Computer
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4990 Accepted Submission(s): 2509
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.
1 1
2 1
3 1
1 1
2
3
4
4
题意：以1为根，建立一棵树，每个节点之间的长度为len,然后求每个节点到叶子的最远距离；
分析:求i节点，两种可能，一种是从i的子树得到最远距离，第二种是从父节点得到最远距离，所以两次dfs,第一次统计所有节点从子树到叶子的最远距离和次远距离，第一次看这道题，不明白次远距离有什么用，看到第二次dfs就明白了，第二次就要判断i是从子树还是父节点过来的，此时已经求出了子树方向的所有最长距离，最要知道父节点方向最长距离就ok了，比较一下嘛，然后父节点的最远距离有两种可能，一种是经过 i 而来的，所以求 i 父节点方向的最远距离就是 i 父节点的次最远距离了，第二种是不经过 i 而来的，所以 i 父节点方向的最远距离就是他
----------------------------------------------------------------------------
2016/3/17更新
今天又看了一遍好费劲，其实第一次dfs1主要是求了根节点1到左右两边节点的最远距离，一个最远，一个次远，然后第二次还是从根节点dfs2，主要就是判断每一个点是从子树来的还是从父节点来的，所以先判断根节点的儿子，因为根节点已经在第一部求出来了到两边的距离。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int Max = + ;
struct Node
{
int to,next,len;
};
Node edge[ * Max];
int head[Max], tol;
int maxn[Max],maxnId[Max]; //最远距离和最远距离对应的序号
int smaxn[Max],smaxnId[Max]; //次远距离和次远距离对应的序号
void add_edge(int a, int b, int len)
{
edge[tol].to = b;
edge[tol].next = head[a];
edge[tol].len = len;
head[a] = tol++;
}
void dfs1(int u, int p)
{
maxn[u] = smaxn[u] = ;
for(int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if(v == p) //如果是父节点跳过
continue;
dfs1(v, u);
if(smaxn[u] < maxn[v] + edge[i].len) //如果子节点的最远距离大于次远距离，就更新次远距离；先更新次远距离，由次远距离和最远距离比较更新最远距离
{
smaxn[u] = maxn[v] + edge[i].len;
smaxnId[u] = v;
if(smaxn[u] > maxn[u])
{
swap(smaxn[u], maxn[u]);
swap(smaxnId[u], maxnId[u]);
}
}
}
}
void dfs2(int u, int p)
{
for(int i = head[u]; i != -; i = edge[i].next)
{
int v = edge[i].to;
if(v == p)
continue;
if(v == maxnId[u]) //如果父节点方向最远距离经过这个子节点
{
if(smaxn[u] + edge[i].len > smaxn[v]) //选择次远距离，因为最远距离经过v点
{
smaxn[v] = smaxn[u] + edge[i].len;
smaxnId[v] = u;
if(maxn[v] < smaxn[v])
{
swap(maxn[v], smaxn[v]);
swap(maxnId[v], smaxnId[v]);
}
}
}
else
{
if(maxn[u] + edge[i].len > smaxn[v])
{
smaxn[v] = maxn[u] + edge[i].len;
smaxnId[v] = u;
if(maxn[v] < smaxn[v])
{
swap(maxn[v], smaxn[v]);
swap(maxnId[v], smaxnId[v]);
}
}
}
dfs2(v, u);
}
}
int main()
{
int n,v,len;
while(scanf("%d", &n) != EOF)
{
tol = ;
memset(head, -, sizeof(head));
for(int i = ; i <= n; i++)
{
scanf("%d%d", &v, &len);
add_edge(i, v, len);
add_edge(v, i, len);
}
dfs1(, -); //向下
dfs2(, -);
for(int i = ; i <= n; i++)
printf("%d\n", maxn[i]);
}
return ;
}