【HDU 2196】 Computer

【题目链接】

            点击打开链接

【算法】

          我们知道，一棵树上离某个节点最远的节点，可能是经过它的祖先，再到那个祖先的某个孩子，或者，是它的那颗子树中，离它最远的一个节点，就不难想到以下算法 ：

           第一遍DFS，搜出每个节点的子树中离它距离最远的孩子的距离和所经过的儿子，离它次远的孩子的距离和所经过的儿子

           第二遍DFS，树形DP求出每个点经过它的祖先节点的最远距离

 【代码】

            

#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010

int i,n,x;
int fa[MAXN],f[MAXN][2],g[MAXN][2],dp[MAXN];
vector< pair<int,int> > e[MAXN];

inline void init()
{
        int i;
        memset(f,0,sizeof(f));
        memset(dp,0,sizeof(dp));
        for (i = 1; i <= n; i++) e[i].clear();
}
inline void dfs1(int x)
{
        int i,y;
        for (i = 0; i < e[x].size(); i++)
        {
                y = e[x][i].first;
                dfs1(y);
                if (f[y][0] + e[x][i].second >= f[x][0])
                {
                        f[x][1] = f[x][0];
                        g[x][1] = g[x][0];
                        f[x][0] = f[y][0] + e[x][i].second;
                        g[x][0] = y;
                } else if (f[y][0] + e[x][i].second > f[x][1])
                {
                         f[x][1] = f[y][0] + e[x][i].second;
                         g[x][1] = y;
                }
        }    
}
inline void dfs2(int x)
{
        int i,y;
        for (i = 0; i < e[x].size(); i++)
        {
                y = e[x][i].first;
                if (g[x][0] != y)
                        dp[y] = max(dp[y],max(dp[x],f[x][0])+e[x][i].second);
                else dp[y] = max(dp[y],max(dp[x],f[x][1])+e[x][i].second);
                dfs2(y);        
        }
}

int main() 
{
        
        while (scanf("%d",&n) != EOF)
        {
                init();
                for (i = 2; i <= n; i++)
                {
                        scanf("%d%d",&fa[i],&x);
                        e[fa[i]].push_back(make_pair(i,x));
                }
                dfs1(1);
                dfs2(1);
                for (i = 1; i <= n; i++) printf("%d
",max(f[i][0],dp[i]));
        }
        
        return 0;
    
}