记录编号	58282	评测结果	AAAAAAAAAA
题目名称	最长链	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2013-04-18 21:19:14	内存使用	3.48 MiB

#include<fstream>
#include<vector>
#include<deque>
#include<cstdio>
using namespace std;
ifstream fi("length.in");
ofstream fo("length.out");
const int infi=100000001;
int n;
class vertexwithweight
{
public:
	int v,w;
};
vector <vertexwithweight> adj[10001];
int d[10001],dd[10001],d1,d2;
bool used[10001];
void dfs(int x)
{
	used[x]=true;
	int y,z;
	z=adj[x].size();
	for(y=0;y<z;y++)
	{
		if(!used[adj[x][y].v])
		{
			used[adj[x][y].v]=true;
			d[adj[x][y].v]=d[x]+adj[x][y].w;
			dfs(adj[x][y].v);
		}
	}
}
void dfs_two(int x)
{
	used[x]=true;
	int y,z;
	z=adj[x].size();
	for(y=0;y<z;y++)
	{
		if(!used[adj[x][y].v])
		{
			used[adj[x][y].v]=true;
			dd[adj[x][y].v]=dd[x]+adj[x][y].w;
			dfs_two(adj[x][y].v);
		}
	}
}
int main()
{
	int i,j,p,q;
	vertexwithweight tmp;
	fi>>n;
	for(i=2;i<=n;i++)
	{
		fi>>p>>q;
		tmp.v=p;tmp.w=q;
		adj[i].push_back(tmp);
		tmp.v=i;tmp.w=q;
		adj[p].push_back(tmp);
	}
	//=========================================处理读入
	/*求出	直径	d1<->d2	*/
	for(i=1;i<=n;i++)used[i]=false,d[i]=0;
	dfs(1);
	d1=1;//d[1]=0;
	for(i=2;i<=n;i++)
		if(d[i]>d[d1])d1=i;
	for(i=1;i<=n;i++)used[i]=false,d[i]=0;
	dfs(d1);
	d2=d1;//d[d1]=0;
	for(i=1;i<=n;i++)
		if(d[i]>d[d2])d2=i;
	/*直径已经求出*/
	for(i=1;i<=n;i++)used[i]=false,dd[i]=0;
	//dd[d2]=0;
	dfs_two(d2);
	/*现在所有点到d1,d2的距离都有了*/
	//fo<<d1<<' '<<d2<<endl;
	for(i=1;i<=n;i++)
	{
		//fo<<i<<' '<<d[i]<<' '<<dd[i]<<endl;
		if(d[i]>dd[i])fo<<d[i]<<endl;
		else fo<<dd[i]<<endl;
	}
	//=========================================
	return 0;
}