HDU-2196: Computer

树形DP

Description

A school bought the first computer some time ago(so this computer's id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.

Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.

Input

Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed $10^9$. Numbers in lines of input are separated by a space.

Output

For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).

Sample Input

5
1 1
2 1
3 1
1 1

Sample Output

3
2
3
4
4

题意：输入数字n，表示有n台电脑，编号1-n，n台电脑组成了无向的树状网络。下面有n-1行输入a和b，分别表示编号为2-n的电脑与a电脑的距离是b，最后输出n个答案，求出每台计算机到其他计算机的最大距离。

分析：树形DP。以1号计算机为根节点，那么对于其他的每个节点来说，最大距离来自自己下方的子节点或者来自父节点。

• 来自子节点的最大距离就是求从该点到最底层的深度；

• 来自父节点的最大距离就要分为两种情况：

  • 父节点的最长距离就是经过这一点来的；
    那么从该节点的与其他节点的最大距离即为：从它到父节点，再从父节点到次长节点的距离之和，与它到本身子节点距离取max；
  • 父节点的最长距离不是经过这一点来的：
    那么从该节点的与其他节点的最大距离即为：从它到父节点，再从父节点到最长节点的距离之和，与它到本身子节点距离取max；

那么我们两次进行dfs，第一次得到每个节点到其子节点最长以及次长的距离，还有最长以及次长距离的来向；第二次dfs得到来自父节点的最大距离并且和第一次求得的距离取max。

• 代码：

#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
struct node
{
    int id,len;
    node(int idd,int lenn)
    {
        id=idd;
        len=lenn;
    }
};
int flen[11111],slen[11111];//最长，次长
int ffro[11111],sfro[11111];//最长来向，次长来向
vector<node>v[11111];
void dfs1(int st,int fa)//父节点为st，子节点作为新的父节点fa
{
    flen[fa]=slen[fa]=0;
    for(int i=0;i<v[fa].size();i++)
    {
        node son=v[fa][i];
        if(son.id==st)  continue;
        dfs1(fa,son.id);
        if(flen[fa]<flen[son.id]+son.len)
        {
            slen[fa]=flen[fa];
            sfro[fa]=ffro[fa];
            flen[fa]=flen[son.id]+son.len;
            ffro[fa]=son.id;
        }
        else if(slen[fa]<flen[son.id]+son.len)
        {
            slen[fa]=flen[son.id]+son.len;
            sfro[fa]=son.id;
        }
    }
}
void dfs2(int fa,int now,int len)
{
    if(now!=1)//非根节点,根节点在dfs1已经处理好了
    {
        if(ffro[fa]!=now)//如果父节点的最长长度不是来自这个子节点
        //对于节点now来说，它的最长长度就是现在它到自身子树的最长距离和它到父节点到其他子树的距离取max，更新来向
        {
            if(flen[now]<flen[fa]+len)
            {
                slen[now]=flen[now];
                sfro[now]=ffro[now];
                flen[now]=flen[fa]+len;
                ffro[now]=fa;
            }
            else if(slen[now]<flen[fa]+len)
            {
                slen[now]=flen[fa]+len;
                sfro[now]=fa;
            }
        }
        //对于now这个子节点来说，它最长的来自：1.自己下方的子节点  2.上面的父节点到其他子树的位置
        //既然要找到now最长的距离，如果父节点最深的地方来自now，那么就需要父节点次深的地方，加上now到父节点的距离，再和now到自身子树距离相比较
        else //如果父节点的最长长度来自now
        {
            if(flen[now]<slen[fa]+len)
            {
                slen[now]=flen[now];
                sfro[now]=ffro[now];
                flen[now]=slen[fa]+len;
                ffro[now]=fa;
            }
            else if(slen[now]<slen[fa]+len)
            {
                slen[now]=slen[fa]+len;
                sfro[now]=fa;
            }
        }
    }
    for(int i=0;i<v[now].size();i++)
    {
        if(v[now][i].id==fa)    continue;
        dfs2(now,v[now][i].id,v[now][i].len);
    }
}
int main()
{
    int n,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<=n;i++)
            v[i].clear();
        memset(flen,0,sizeof(flen));
        memset(slen,0,sizeof(slen));
        for(int i=2;i<=n;i++)
        {
            scanf("%d%d",&a,&b);
            v[i].push_back(node(a,b));
            v[a].push_back(node(i,b));
        }
        dfs1(0,1);//找到每个节点向下延伸的最长以及次长的距离和其来向
        dfs2(0,1,0); //fa,now,len
        for(int i=1;i<=n;i++)
            printf("%d\n",flen[i]);
    }
    return 0;
}