E-Computer

描述
一所学校不久前买了第一台电脑（所以这台电脑的ID是1）。近年来，学校购买了N-1新电脑。每台新电脑都连接到一台先前安装的电脑上。学校的管理人员担心网络运行缓慢，希望知道第i台计算机需要发送信号的最大距离si（即到最远计算机的电缆长度）。您需要提供此信息。

提示：示例输入与此图对应。从图中，你可以看到计算机4离1最远，所以s1=3。计算机4和5是距离2最远的，所以s2=2。计算机5是离3最远的，所以s3=3。我们也得到了s4=4，s5=4。

输入
输入文件包含多组测试样例。在每组样例中，第一行中都有自然数n（n<=10000），然后是（n-1）行，其中包含对计算机的描述。第i行包含两个自然数-第i计算机所连接的计算机和用于连接的电缆长度。电缆总长度不超过10^9。输入行中的数字用空格分隔。

输出
对于每组样例，输出n行。第i行第i台计算机的到其他计算机的最大长度Si（1<=i<=n）。

样例输入

样例输出

提示
示例输入与此图对应。从图中，你可以看到计算机4离1最远，所以s1=3。计算机4和5是距离2最远的，所以s2=2。计算机5是离3最远的，所以s3=3。我们也得到了s4=4，s5=4。

这个一看见就直接蒙圈了Woc这咋搞，想了好久还是csdn了，从一个点出发寻找到距离它最远的点，然后在从这个点出发寻找距离它最远的点中间记录每个节点的最远路程，这样算的的路径都是距离该节点的最远路径，然后再从距离这个点的最远的点在进行dfs还更新节点距离，那么最后的结果就是了

#include<iostream>
#include<algorithm> 
#include<iostream>
#include<cstring>
#include<vector>

using namespace std;

typedef pair<int,int> pa;
int n,maxlen,s;
vector<pa>v[100100];
int dp[100100];

int dfs(int x,int y,int l)
{
	if(maxlen<=l)
	{
		maxlen=l;
		s=x;
	}
	pa p;
	for(int i=0;i<v[x].size() ;i++)
	{
		p=v[x][i];
		if(p.first ==y) continue;
		else
		{	
			dfs(p.first ,x,l+p.second);
			dp[p.first]=max(dp[p.first],l+p.second);
		}
	}
}

int main()
{
	while(cin>>n)
	{
		int x,y;
		memset(dp,0,sizeof dp);
		for(int i=0;i<=n;i++) v[i].clear() ;
		for(int  i=2;i<=n;i++)
		{
			cin>>x>>y;
			v[x].push_back(make_pair(i,y));
			v[i].push_back(make_pair(x,y));  
		}
		s=0;
		maxlen=0;
		maxlen=0;
		dfs(1,-1,0);
		dfs(s,-1,0);
		dfs(s,-1,0);
		for(int i=1;i<=n;i++) cout<<dp[i]<<endl;
	}
	return 0;
}