P1122 最大子树和————树形DP

题解：本题主要考查树形DP。 简要题意：给定一棵$N$个节点的无根树，点有点权，点权有正有负，求这棵树的联通块的最大权值之和是多少。 1.树形DP：$f[p]$表示以$p$为根且包含u的最大权联通块 因为点权有正有负，负的点就可以不取，所以用$0$比较： $f[p]+=max(0,f[k]);$($k$为$p$的儿子) 代码如下：

#include<iostream> #include<algorithm> using namespace std; struct N { int start,to; }t[100001]; int h[100001],f[100001],a[100001]; int n,ans,x,y,root,P=0; void add(int start,int to) { t[++P].to=to; t[P].start=h[start]; h[start]=P; } void dfs(int p,int father) { f[p]=a[p]; for(int i=h[p];i;i=t[i].start) { int k=t[i].to; if(k!=father) { dfs(k,p); f[p]+=max(0,f[k]); } } ans=max(ans,f[p]); } int main() { cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n-1;i++) { cin>>x>>y; add(x,y);add(y,x); } dfs(1,0); cout<<ans<<endl; return 0; }