【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][],g[MAXN][],dp[MAXN];

vector< pair<int,int> > e[MAXN];

inline void init()

{

        int i;

        memset(f,,sizeof(f));

        memset(dp,,sizeof(dp));

        for (i = ; i <= n; i++) e[i].clear();

}

inline void dfs1(int x)

{

        int i,y;

        for (i = ; i < e[x].size(); i++)

        {

                y = e[x][i].first;

                dfs1(y);

                if (f[y][] + e[x][i].second >= f[x][])

                {

                        f[x][] = f[x][];

                        g[x][] = g[x][];

                        f[x][] = f[y][] + e[x][i].second;

                        g[x][] = y;

                } else if (f[y][] + e[x][i].second > f[x][])

                {

                         f[x][] = f[y][] + e[x][i].second;

                         g[x][] = y;

                }

        }

}

inline void dfs2(int x)

{

        int i,y;

        for (i = ; i < e[x].size(); i++)

        {

                y = e[x][i].first;

                if (g[x][] != y)

                        dp[y] = max(dp[y],max(dp[x],f[x][])+e[x][i].second);

                else dp[y] = max(dp[y],max(dp[x],f[x][])+e[x][i].second);

                dfs2(y);

        }

}

int main()

{

        while (scanf("%d",&n) != EOF)

        {

                init();

                for (i = ; i <= n; i++)

                {

                        scanf("%d%d",&fa[i],&x);

                        e[fa[i]].push_back(make_pair(i,x));

                }

                dfs1();

                dfs2();

                for (i = ; i <= n; i++) printf("%d\n",max(f[i][],dp[i]));

        }

        return ;

}

巴特西

【HDU 2196】 Computer

最新文章

热门文章