题解 P1122 【最大子树和】

wzmszjw · 2015-11-01 09:31:55 · 题解

直接dp，建棵树，dp[i]表示取以i为根的子树最大的收益是多少，因为要联通，所以更新是dp[i]=max(dp[i],dp[i]+dp[j])，j是i的儿子，最后循环一遍n，看dp值最大是多少就可以了。

[codec ]#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <algorithm>  
using namespace std;  
const int M=32100;  
int n,s;  
int to[M],w[M],first[M],next[M],dp[M];  
void add(int x,int y){  
    to[++s]=y; next[s]=first[x]; first[x]=s;  
}  
void dfs(int x,int fa){  
    dp[x]=w[x];  
    for(int i=first[x];i>0;i=next[i]){  
        int y=to[i];  
        if(y==fa) continue;  
        dfs(y,x);  
        if(dp[y]>0) dp[x]+=dp[y];  
    }  
}  
int main()  
{  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++){  
        scanf("%d",&w[i]);  
    }  
    for(int i=1;i<=n-1;i++){  
        int a,b;  
        scanf("%d%d",&a,&b);  
        add(a,b);  
        add(b,a);  
    }  
    dfs(1,0);  
    int ans=-16000010;  
    for(int i=1;i<=n;i++) if(dp[i]>ans) ans=dp[i];  
    printf("%d",ans);  
}  [/codec ]