hdu2196 Computers 树形DP

这题自己没想出来，，连续做了几天的树形DP结果反而思路被限制了，现在想来这题其实不难= =！主要是既要存 i 到叶子的最大值以及取得这个最大值的关联儿子节点，还要存取得次大的值这些信息。因为最后扩展到全部节点的时候可能出现 j 的父亲节点 i 恰好是 i 取得max的关联儿子节点，这样状态就无法转移了，于是我们就需要一个次大值的信息来解决这种问题。（最大与次大严格不重复）接下来就很简单了

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;

int head[10050];
struct NODE
{
    int to,len,next;
}edge[20000];
int N;
int imax[10050],imax2[10050];
int id[10050],id2[10050];

void dfs1(int x)
{
    imax[x]=imax2[x]=0;
    int i,to;
    for(i=head[x];i!=-1;i=edge[i].next)
    {
        to=edge[i].to;
        dfs1(to);
        if(imax2[x] < imax[to] + edge[i].len)
        {
            imax2[x]=imax[to] + edge[i].len;
            id2[x]=to;
            if(imax[x] < imax2[x])
            {
                swap(imax[x],imax2[x]);
                swap(id[x],id2[x]);
            }
        }
    }
}

void dfs2(int x)
{
    int i,to;
    for(i=head[x];i!=-1;i=edge[i].next)
    {
        to=edge[i].to;
        if(to == id[x])
        {
            if(edge[i].len + imax2[x] > imax2[to])
            {
                imax2[to]=edge[i].len+imax2[x];
                id2[to]=x;
                if(imax2[to] > imax[to])
                {
                    swap(imax2[to],imax[to]);
                    swap(id[to],id2[to]);
                }
            }
        }
        else
        {
            if(edge[i].len + imax[x] > imax2[to])
            {
                imax2[to]=edge[i].len+imax[x];
                id2[to]=x;
                if(imax2[to] > imax[to])
                {
                    swap(imax2[to],imax[to]);
                    swap(id[to],id2[to]);
                }
            }
        }
        dfs2(to);
    }
}

int main()
{
    while(~scanf("%d",&N))
    {
        int i,j,len;
        int c;
        memset(head,-1,sizeof(head));
        for(i=2,c=0;i<=N;i++)
        {
            scanf("%d %d",&j,&len);
            edge[c].to=i,edge[c].len=len,edge[c].next=head[j],head[j]=c++;
        }
        dfs1(1);
        dfs2(1);
        for(i=1;i<=N;i++) printf("%d\n",imax[i]);
    }
}

hdu2196 Computers 树形DP,布布扣,bubuko.com

hdu2196 Computers 树形DP

原文：http://blog.csdn.net/alone_l/article/details/20565315