P1122 最大子树和（树形dp）
大水题
随便找一个点做根，蓝后累计子树和。
子树和<0的话不取就行了
顺便找个最大值输出
end.
#include<iostream> #include<cstdio> #include<cstring> #include<cctype> #define re register using namespace std; void read(int &x){ char c=getchar();x=0; bool f=1; while(!isdigit(c)) f=(f&&c!='-'),c=getchar(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar(); x=f?x:-x; } int max(int &a,int &b){return a>b?a:b;} #define N 16002 int n,f[N],val[N],ans=-2147483647; int cnt,hd[N],nxt[N<<1],ed[N],poi[N<<1]; void adde(int x,int y){ nxt[ed[x]]=++cnt; hd[x]=hd[x]?hd[x]:cnt; ed[x]=cnt; poi[cnt]=y; } void dfs(int x,int fa){ f[x]=val[x]; for(int i=hd[x];i;i=nxt[i]){ int to=poi[i]; if(to==fa) continue; dfs(to,x); if(f[to]>0) f[x]+=f[to];//子树和>0才取 }ans=max(ans,f[x]); } int main(){ read(n); int q1,q2; for(re int i=1;i<=n;++i) read(val[i]); for(re int i=1;i<n;++i){ read(q1); read(q2); adde(q1,q2); adde(q2,q1); }dfs(1,0); printf("%d",ans); return 0; }