Tree of life ( Tree shape DP)



Data range

1≤n≤10^5,
The absolute value of the score of each node shall not exceed  10^6.

sample input ：
5 1 -2 -3 4 5 4 2 3 1 1 2 2 5
sample output ：
8
  analysis ： This problem requires us to find the most common block in the tree , We can define f[i] For i Is the value of the most common block in the subtree of the root
, The result is f[1~n] Maximum in , Tree shape DP The process is relatively simple , First order f[i]=w[i], That is to make this connected block contain only its own point , Then, as long as the value of the most common block in the subtree with the child node as the root is greater than 0, Just add , Follow this procedure dp You can find the answer , Detail reference code ：
#include<cstdio> #include<iostream> #include<cstring> #include<vector>
#include<algorithm> #include<map> #include<cmath> #include<queue> using
namespace std; #define int long long const int N=1e5+10; int
w[N*2],f[N],e[N*2],ne[N*2],h[N],idx;//f[i] Express with i Is the maximum value in the connected block of the root void add(int x,int y)
{ e[idx]=y; ne[idx]=h[x]; h[x]=idx++; } int dp(int x,int father) { f[x]=w[x];
for(int i=h[x];i!=-1;i=ne[i]) { int j=e[i]; if(j==father) continue;
f[x]+=max(dp(j,x),(int)0); } return f[x]; } signed main() { int n; cin>>n;
for(int i=1;i<=n;i++) scanf("%lld",&w[i]); memset(h,-1,sizeof h); for(int
i=1;i<n;i++) { int u,v; scanf("%lld%lld",&u,&v); add(u,v);add(v,u); } dp(1,0);
int ans=-0x3f3f3f3f; for(int i=1;i<=n;i++) ans=max(ans,f[i]);
printf("%lld",ans); return 0; }

Technology
©2020-2025 ioDraw All rights reserved, Privacy Policy