sgu 143 Long Live the Queen 樹狀DP

傳送門:sgu 143 Long Live the Queen

題目大意：

給出一棵樹找出這個子樹價值的最大值

解題思路

簡單的樹狀DP，判斷目前節點的子樹，如果這個子樹大于0就加上，如果小于0就放棄！

AC代碼

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN =  + ;
const int INF  = ;
int head[MAXN],e,w[MAXN],dp[MAXN][];
int ans[MAXN];
struct Edge{
    int v,nxt,w;
}E[MAXN<<];
void init()
{
    e = ;
    memset(head,-,sizeof head);
}
void add(int u,int v)
{
    E[e].v = v;
    E[e].nxt = head[u];
    head[u] = e++;
}
int DFS(int u,int pre)
{
    ans[u] = w[u];
    for(int i=head[u];~i;i=E[i].nxt){
        int tmp = ;
        int v =E[i].v;
        if(v==pre)continue;
        tmp = DFS(v,u);
        if(tmp>)  ans[u] += tmp;
    }
    return ans[u];
}
int main()
{
    int N;
    int u,v;
    scanf("%d",&N);
    init();
    for(int i=;i<=N;i++)
        scanf("%d",&w[i]);
    for(int i=;i<N;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    DFS(,-);
    int MAX = -INF;
    for(int i=;i<=N;i++)
        if(ans[i]>MAX) MAX = ans[i];
    printf("%d",MAX);
    return ;
}