Computer
题目链接：
http://acm.hdu.edu.cn/submit.php?pid=2196
题意：
学校里有一台电脑(编号为1)，这些年来又陆续买了(N-1)台电脑，每一台新电脑都要和一台已经存在的电脑连接，构成了一棵以1为根的树，求树上每个节点到所有叶子节点的距离的最大值。
题解：
先跑一遍DFS记录下val1（“以V为根的子树”的最远叶子节点的距离）和val2（与路径[V到其最远叶子节点]没有公共路径的最远的叶子节点的距离）
可以发现 当前节点V到其他所有点的最大值可能由三种情况得到:
①其父亲节点Fa到以“Fa为根的子树”的最远叶子节点的距离val1（注意这里，当这个最远节点同时也是V的最远节点时不可取，应取Fa对应的val2）+Fa到V的边权
②当前节点到其下的叶子节点的最大距离val1
③其父亲节点Fa到除了“以Fa为根的子树”上的节点外 最远的节点的距离（设其为fa）+Fa到V的边权
可以知道①和②的答案都已经在第一次的DFS中求出来了，要求的就是③的值
再进行一遍DFS，即可得到答案
代码
#include<stdio.h>
#include<vector>
using namespace std;
const int N=10001;
struct edge
{
int to,val;
edge(int x=0,int y=0)
{
to=x,val=y;
}
};
int mmax(int a,int b,int c)
{
return a>b?(a>c?a:c):(b>c?b:c);
}
vector<edge>q[N];
struct node
{
int value,fa,val1,val2,son1,son2;
}t[N];
void Dfs_Findval(int id)
{
int m=1,son1,son2;
for(int i=0;i<q[id].size();++i)
{
int to=q[id][i].to;
Dfs_Findval(to);
int val=q[id][i].val+t[to].val1;
int son=t[to].son1;
if(val>t[id].val1)
{
t[id].val2=t[id].val1;
t[id].son2=t[id].son1;
t[id].val1=val;
t[id].son1=son;
}
else if(val>t[id].val2)
{
t[id].val2=val;
t[id].son2=son;
}
m=0;
}
if(m)t[id].son1=t[id].son2=id;
return ;
}
void Dfs_Findans(int id)
{
for(int i=0;i<q[id].size();++i)
{
int to=q[id][i].to;
int V=q[id][i].val;
if(t[to].son1!=t[id].son1)
{
t[to].fa=mmax(t[id].val1+V,t[id].fa+V,0);
t[to].value=mmax(t[to].val1,t[id].fa+V,t[id].val1+V);
}
else
{
t[to].fa=mmax(t[id].val2+V,t[id].fa+V,0);
t[to].value=mmax(t[to].val1,t[id].fa+V,t[id].val2+V);
}
Dfs_Findans(to);
}
}
void solve()
{
int n,x,y;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;++i)
{
q[i].clear();
t[i].val1=t[i].val2=t[i].fa=0;
}
for(int i=2;i<=n;++i)
{
scanf("%d%d",&x,&y);
q[x].push_back(edge(i,y));
}
Dfs_Findval(1);
Dfs_Findans(1);
printf("%d
",t[1].val1);
for(int i=2;i<=n;++i)
printf("%d
",t[i].value);
}
}
int main()
{
solve();
}