ZOJ_2834 树形DP

题目意思太罗嗦，不解释了。这道题一开始一直Segmentation Fault，问了秦总才发现可能是数组放在dfs里面的关心后来又wa了无数次，结果是因为它居然可以是个森林！！！简直报警了，题目中明明说的是Koopa的所有儿子，居然还可以存在森林。唉。。。

这道题好事蛮不错的一道题，每一个点有三种状态：dp[i][0]，dp[i][1]，dp[i][2]。dp[i][1]代表第i个人刚刚被干掉，第i个节点及其子树的最大值。dp[i][0]代表第i个节点即所有节点的t[i]值之和。dp[i][2]代表的是第i个节点没有被干掉所能干掉其子树的最大值和。

下面来写转移方程：

dp[u][0] = t[u] + sum{dp[v][0]};

dp[u][2] = max{dp[v][0] + sum{dp[w][2] | w != v} = max{dp[v][0]-dp[v][2])}+ sum{dp[v][2]}; 这两个v相互独立

dp[u][1] = max{dp[v][0]-dp[v][2] + dp[w][1] - dp[w][2] | w != v} + sum{dp[v][2]};

注意下一边界条件就可以开始写了。。。算 dp[v][0]-dp[v][2]+dp[w][1]-dp[w][2]的最大值的时候有一个小技巧，直接看我的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define FOR(i,x,y) for(int i = x;i < y;i ++)

using namespace std;

const int MAXN = 2222;

int n,dp[MAXN][3],t[MAXN],head[MAXN],edge_cnt;    //dp[i][0]表示i个节点和他的所有子树都被杀了，dp[i][1]表示第一次i个节点被杀了，dp[i][2]表示i个节点没被杀
int st[MAXN];

struct Edge{
    int to,next;
}edge[MAXN<<1];

bool cmp(int x,int y)   {return x>y;}

void add_edge(int u,int v){
    edge[edge_cnt].to = v;
    edge[edge_cnt].next = head[u];
    head[u] = edge_cnt++;
}

void dfs(int u,int fa){
    dp[u][0] = dp[u][1] = t[u]; dp[u][2] = 0;
    int cnt = 0;
    int dp2 = -1;
    int sum = 0;
    int dp00 = -1,dp01 = -1,dp10 = -1,dp11 = -1; ///dp00 代表dp[v][0]-dp[v][2]的最大值，dp01代表第二大值，dp10同理
    for(int i = head[u];i != -1;i = edge[i].next){
        int v = edge[i].to;
        if(v == fa) continue;
        dfs(v,u);
        dp[u][0] += dp[v][0];
        sum += dp[v][2];
        if((dp[v][0]-dp[v][2]) >= dp00){
            dp01 = dp00;
            dp00 = dp[v][0]-dp[v][2];
        }
        else dp01 = max(dp01,t[v]);
        if(dp[v][1]-dp[v][2] >= dp10){
            dp11 = dp10;
            dp10 = dp[v][1]-dp[v][2];
        }
        else dp11 = max(dp11,dp[v][1]-dp[v][2]);
        dp2 = max(dp2,dp[v][0]-dp[v][2]+dp[v][1]-dp[v][2]);
        cnt++;
    }
    if(!cnt)    return;
    if(cnt == 1){
        dp[u][1] += sum+dp00;
        dp[u][2] += sum+dp00;
    }
    else{
        if(dp00 + dp10 == dp2) {
            if(dp01 == dp00 || dp11 == dp10)
                dp[u][1] += sum+dp2;
            else
                dp[u][1] += sum+max(dp00+dp11,dp01+dp10);
        }
        else
            dp[u][1] += sum + dp00 + dp10;
        dp[u][2] += sum+dp00;
    }
    return;
}

int dfs2(int u,int fa){
    int ans = t[u];
    for(int i = head[u];i != -1;i = edge[i].next){
        int v = edge[i].to;
        if(v == fa) continue;
        ans += dfs2(v,u);
    }
    return ans;
}

int main()
{
    freopen("test.in","r",stdin);
    while(~scanf("%d",&n) && n){
        memset(head,-1,sizeof(head));
        edge_cnt =0;
        FOR(i,0,n)  scanf("%d",&t[i]);
        int to;
        int st_cnt = 0;
        FOR(i,0,n){
            scanf("%d",&to);
            if(to == -1){
                st[st_cnt++] = i;
                continue;
            }
            add_edge(i,to);
            add_edge(to,i);
        }
        int ans = 0;
        FOR(i,0,st_cnt-1)   ans += dfs2(st[i],-1);
        dfs(n-1,-1);
        printf("%d
",ans+dp[n-1][1]);
    }
    return 0;
}