树形DP刷题小记
最大子树和
链接:P1122 最大子树和
算法分析
典范的树形DP，要联合贪心的思想。f[x]存储以x为根可以得到的最大漂亮值,若子树的漂亮值小于零，即对效果有害，应减去。
状态转移方程: f [ x ] + = f [ y ] > 0 ? f [ y ] : 0 f[x]+=f[y]>0?f[y]:0 f[x]+=f[y]>0?f[y]:0
Code：
[code]#includeusing namespace std;inline int Read(){ int dx=0,fh=1; char c; c=getchar(); while(c'9'){ if(c=='-') fh=-1; c=getchar(); } while(c='0'){ dx=dx*10+c-'0'; c=getchar(); } return dx*fh;}struct node{ int to,next;}edg[170000];int n,beauty[170000],h[170000],cnt,ans,f[170000];void add(int a,int b){ ++cnt; edg[cnt].to=b; edg[cnt].next=h[a]; h[a]=cnt;}void dfs(int u){ f=beauty; for(int i=h;i;i=edg.next){ int v=edg.to; dfs(v); if(f[v]>0) f+=f[v]; } ans=max(ans,f);}int main(){ n=Read(); for(int i=1;i |
