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("%d\n",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

*/

C. Ilya And The Tree

写法还是比较容易想到，但是这么暴力的写法不是那么的敢写。

就直接枚举了每一个点上面的点的所有的情况，对于这个点不放进去特判一下，然后排序去重提高效率。

注意dp[v]一开始存的是从根节点到这个节点都选的情况，这样才好往后转移。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 4e5 + 10;
typedef long long ll;
int dp[maxn],head[maxn],cnt = 0,a[maxn];
vector<int>vec[maxn];
struct node
{
    int u,v,nxt;
    node(int u=0,int v=0,int nxt=0):u(u),v(v),nxt(nxt){}
}ex[maxn];

void init()
{
    memset(head,-1,sizeof(head));
    cnt = 0;
}
void add(int u,int v)
{
    ex[cnt] = node(u,head[u]);
    head[u] = cnt++;
    ex[cnt] = node(v,u,head[v]);
    head[v] = cnt++;
}

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b,a%b);
}

void dfs(int u,int pre)
{
    for(int i=head[u];i!=-1;i=ex[i].nxt)
    {
        int v = ex[i].v;
        if (v == pre) continue;
        dp[v] = gcd(dp[u],a[v]);
        vec[v].push_back(dp[u]);
        for(int j=0;j<vec[u].size();j++) vec[v].push_back(gcd(vec[u][j],a[v]));
        sort(vec[v].begin(),vec[v].end());
        vec[v].erase(unique(vec[v].begin(),vec[v].end()),vec[v].end());
        dfs(v,u);
    }
}

int main()
{
    init();
    int n;
    scanf("%d",&n);
    for (int i = 1; i <= n; i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    dp[1] = a[1];
    vec[1].push_back(0);
    dfs(1,-1);
    for (int i = 1; i <= n; i++) dp[i] = max(dp[i],vec[i].back());
    for (int i = 1; i <= n; i++) printf("%d ",dp[i]);
    return 0;
}