#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
#define __builtin_popcount __builtin_popcountll
using ll=long long; using ld=long double;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); const ld pi=acos(0)*2;
template <typename T> inline void read(T &x){char c; bool nega=0; while((!isdigit(c=getchar()))&&(c!='-')); if(c=='-'){nega=1; c=getchar();} x=c-48; while(isdigit(c=getchar())) x=x*10+c-48; if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10); putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){ putchar('-'); x=-x;} writep(x);}
template <typename T> inline void writeln(T x){write(x); putchar('\n');}
#define taskname "Chase"
const ll inf=1e18;
ll p[100001];
ll pp[100001];
ll c[100001];
vector <int> g[100001];
ll f[100001][101][2];
ll h[100001][101];
void update(ll *p, ll a){
if(p[0]<a){
p[1]=p[0];
p[0]=a;
}
else if(p[1]<a) p[1]=a;
}
bool done[100001];
int n, k;
ll ans=0;
void dfs(int u){
done[u]=1;
for(int &v: g[u]) if(done[v]){
swap(v, g[u].back());
g[u].pop_back();
break;
}
for(int v: g[u]) c[u]+=p[v];
for(int v: g[u]){
pp[v]=p[u];
dfs(v);
// FOR(i, 1, k) f[v][i][0]=max(f[v][i][0], f[v][i-1][0]);
// FOR(i, 0, k) update(f[u][i], max(f[v][i][0], (i?f[v][i-1][0]:-inf)+c[v]));
FOR(i, 1, k) h[v][i]=max(h[v][i], h[v][i-1]);
FOR(i, 0, k) h[u][i]=max(h[v][i], (i?h[v][i-1]:-inf)+c[u]-p[v]+pp[u]);
}
h[u][1]=max(h[u][1], c[u]+pp[u]);
FOR(i, 0, k){
ans=max(ans, h[u][i]);
// ans=max(ans, f[u][i][0]);
// if(i) ans=max(ans, f[u][i-1][0]+c[u]+pp[u]);
}
// for(int v: g[u]){
// FOR(i, 0, k){
// int j=k-i;
// if(f[u][i][0]==max(f[v][i][0], (i?f[v][i-1][0]:-inf)+c[v])){
// ans=max(ans, f[u][i][1]+max(h[v][j], (j?h[v][j-1]:-inf)+c[u]-p[v]+pp[u]));
// }
// else{
// ans=max(ans, f[u][i][0]+max(h[v][j], (j?h[v][j-1]:-inf)+c[u]-p[v]+pp[u]));
// }
// }
// }
}
void add_edge(int u){
for(int v: g[u]) add_edge(v);
for(int v: g[u]) g[v].pb(u);
}
int main(){
#ifdef Aria
if(fopen(taskname".in", "r"))
freopen(taskname".in", "r", stdin);
#endif // Aria
read(n);
read(k);
FOR(i, 1, n) read(p[i]);
{
int u, v;
FFOR(i, 1, n){
read(u);
read(v);
g[u].pb(v);
g[v].pb(u);
}
}
dfs(1);
ll myans=ans;
FOR(i, 2, n){
add_edge(i-1);
FOR(j, 1, n) FOR(x, 0, k) f[j][x][0]=f[j][x][1]=0;
FOR(i, 1, n) done[i]=0;
FOR(i, 1, n) c[i]=0;
FOR(i, 1, n) pp[i]=0;
FOR(j, 1, n) FOR(x, 0, k) h[j][x]=0;
dfs(i);
}
// if(ans!=myans){
// while(true){
// int k;
// writeln(k);
// }
// }
// else
writeln(ans);
}
Compilation message
chase.cpp: In function 'int main()':
chase.cpp:93:8: warning: unused variable 'myans' [-Wunused-variable]
ll myans=ans;
^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4043 ms |
248700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
2688 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
2688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
