hdu-5834 Magic boy Bi Luo with his excited tree 树形dp

http://acm.hdu.edu.cn/showproblem.php?pid=5834

神级烦的一个树形dp

dp1【0】【x】代表从x结点向下走并且回到x结点的最大值

dp1【1】【x】代表从x结点向下走，并且不回到x结点的最大值（去向某一个子树分支，通过index【x】记录）

dp1【1】【x】代表从x结点向下走，并且不回到x结点的第二大值

dp2【0】【x】代表从x结点向父节点走，并且回来的最大值

dp2【1】【x】代表从x结点向父节点走，并且不回来的最大值

带了几个调试时举得样例

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
const int inf=0x3f3f3f3f;
long long dp1[3][maxn];
long long index[maxn];
long long dp2[2][maxn];
long long ans[maxn];
struct node
{
    int ne,cost;
};
int n;
int v[maxn];
vector<node>w[maxn];

void dfs1(int x,int fa)
{
	dp1[0][x]=v[x];
    for(int i=0;i<w[x].size();i++)
    {
        node ne=w[x][i];
        if(ne.ne==fa)
            continue;
        dfs1(ne.ne,x);
        if(dp1[0][ne.ne]-2*ne.cost>0)
        dp1[0][x]+=dp1[0][ne.ne]-2*ne.cost;
    }
    dp1[2][x]=dp1[1][x]=dp1[0][x];
    for(int i=0;i<w[x].size();i++)
    {
    	node ne=w[x][i];
    	if(ne.ne==fa)
    		continue;
    	int now=dp1[0][x]-max(dp1[0][ne.ne]-2*ne.cost,0ll)+dp1[1][ne.ne]-ne.cost;
    	if(now>=dp1[1][x])
    	{
    		dp1[2][x]=dp1[1][x];
    		index[x]=ne.ne;
    		dp1[1][x]=now;
		}
		else if(now>=dp1[2][x])
		{
			dp1[2][x]=now;
		}
	}
}
void dfs2(int x,int fa)
{
    int i,k;
    for(i=0;i<w[x].size();i++)
    {
        node ne=w[x][i];
        if(ne.ne==fa)
            continue;
        int self=dp1[0][ne.ne]-2*ne.cost;
        if(self<0)
        self=0;
    	dp2[0][ne.ne]=max(dp2[0][ne.ne],dp1[0][x]-self+dp2[0][x]-2*ne.cost);
		if(ne.ne==index[x])
		{
			dp2[1][ne.ne]=max(dp2[1][ne.ne],dp2[0][x]-ne.cost+dp1[2][x]-self);
		}
		else
		{
			dp2[1][ne.ne]=max(dp2[1][ne.ne],dp2[0][x]-ne.cost+dp1[1][x]-self);
		}
		dp2[1][ne.ne]=max(dp2[1][ne.ne],dp1[0][x]-self+dp2[1][x]-ne.cost);
		dfs2(ne.ne,x);
	}
}

int main()
{
    int tca=1,T,i;
    cin>>T;
    while(T--)
    {
      	scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&v[i]);
        }
        int u1,u2,c;
        for(i=1;i<n;i++)
        {
            scanf("%d %d %d",&u1,&u2,&c);
            node tt;
            tt.ne=u2;
            tt.cost=c;
            w[u1].push_back(tt);
            tt.ne=u1;
            w[u2].push_back(tt);
        }
        printf("Case #%d:n",tca++);
        for(i=0;i<=n;i++)
        dp1[0][i]=dp1[1][i]=dp1[2][i]=dp2[0][i]=dp2[1][i]=0,index[i]=-1;

  /*      node tt;
        tt.ne=1;
        v[0]=0;
        tt.cost=0;
        w[0].push_back(tt);
		dfs1(0,0);
        dfs2(0,0);*/
        dfs1(1,0);
        dfs2(1,0);
        for(i=1;i<=n;i++)
        {
   //         cout<<dp1[0][i]<<" "<<dp1[1][i]<<" "<<dp2[0][i]<<" "<<dp2[1][i]<<endl;
            printf("%dn",max(dp1[0][i]+dp2[1][i],dp1[1][i]+dp2[0][i]));
        }
        for(i=0;i<=n;i++)
        w[i].clear();
    }
    return 0;
}
/*

5
2 6 3 3 4
1 2 5
1 3 1
1 4 4
1 5 2


5
3 3 3 3 3
1 2 1
1 3 1
1 4 1
1 5 1


10
2 2 2 2 2 2 2 4 4 4
1 2 1
2 3 1
2 4 1
2 5 1
2 6 1
1 7 5
7 8 1
7 9 1
7 10 1

*/