P1122 最大子树和（树形dp）

P1122 最大子树和

大水题

随便找一个点做根，蓝后累计子树和。

子树和<0的话不取就行了

顺便找个最大值输出

end.

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cctype>

#define re register

using namespace std;

void read(int &x){

    char c=getchar();x=; bool f=;

    while(!isdigit(c)) f=(f&&c!='-'),c=getchar();

    while(isdigit(c)) x=(x<<)+(x<<)+(c^),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=-;

int cnt,hd[N],nxt[N<<],ed[N],poi[N<<];

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]>) f[x]+=f[to];//子树和>0才取

    }ans=max(ans,f[x]);

}

int main(){

    read(n); int q1,q2;

    for(re int i=;i<=n;++i) read(val[i]);

    for(re int i=;i<n;++i){

        read(q1); read(q2);

        adde(q1,q2); adde(q2,q1);

    }dfs(,);

    printf("%d",ans);

    return ;

}