#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
typedef tree<pair<lli,int>,null_type,less<pair<lli,int>>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int n,m;
vi al[501],v;
int dp[501][501],lev[500],ans=0,val[501],par[501][11],dis[501][501],din[501],dout[501],ti=0;
bool isa(int u,int v)
{
return (din[u]<=din[v])&&(dout[u]>=dout[v]);
}
int lca(int u,int v)
{
if(isa(u,v))
return(u);
if(isa(v,u))
return(v);
for(int i=10;i>=0;--i)
if(!isa(par[u][i],v))
u=par[u][i];
return(par[u][0]);
}
void dfs(int node,int p,int l)
{
par[node][0]=p;
lev[node]=l;
din[node]=ti++;
for(int i=1;i<11;++i)
par[node][i]=par[par[node][i-1]][i-1];
for(int i=0;i<al[node].size();++i)
if(al[node][i]!=p)
dfs(al[node][i],node,l+1);
dout[node]=ti++;
}
void dfs2(int node,int p)
{
dp[node][0]=(node==1)?0:-1;
for(int t=1;t<=m;++t)
{
dp[node][t]=(node==1)?val[node]:-1;
for(int i=0;i<v.size();++i)
{
if(dis[v[i]][node]>t-1||dp[v[i]][t-1-dis[v[i]][node]]==-1)
continue;
dp[node][t]=max(dp[node][t],val[node]+dp[v[i]][t-1-dis[v[i]][node]]);
}
ans=max(ans,dp[node][t]);
}
v.pb(node);
for(int i=0;i<al[node].size();++i)
if(al[node][i]!=p)
dfs2(al[node][i],node);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(int i=1;i<=n;++i)
cin>>val[i];
for(int i=0;i<n-1;++i)
{
int f,s;
cin>>f>>s;
al[f].pb(s);
al[s].pb(f);
}
dfs(1,1,0);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
int l=lca(i,j);
dis[i][j]=(lev[i]-lev[l])+lev[j]-lev[l];
}
dis[0][i]=lev[i];
dis[i][0]=lev[i];
}
dfs2(1,1);
cout<<ans<<endl;
return(0);
}
Compilation message
dostavljac.cpp: In function 'void dfs(int, int, int)':
dostavljac.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
dostavljac.cpp: In function 'void dfs2(int, int)':
dostavljac.cpp:56:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<v.size();++i)
~^~~~~~~~~
dostavljac.cpp:65:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<al[node].size();++i)
~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
512 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
640 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
1152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
1536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
2068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
312 ms |
2296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
