两次搜索的方法
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int N,V[10100];
vector<int>son[10100]; //图
int MAX[10100],MAXN[10100]; //最大值及其标号
int SMAX[10100],SMAXN[10100]; //次大值及其标号
bool vis[10100]; //标记访问状态
void dfs1(int n) //在以n为根节点的子树上求出节点n到叶子节点距离的最大值
{
MAX[n]=SMAX[n]=0;
int len=son[n].size();
for(int i=0;i<len;i++)
{
int k=son[n][i]; //儿子标号 - -
dfs1(k);
if(SMAX[n]<MAX[k]+V[k])
{
SMAX[n]=MAX[k]+V[k];
SMAXN[n]=k;
if(SMAX[n]>MAX[n]){
swap(SMAX[n],MAX[n]);
swap(SMAXN[n],MAXN[n]);
}
}
}
}
void dfs2(int n) //求出n的儿子们在树中能延伸的最大距离(n的最大距离及次大距离已得到)
{
int len=son[n].size();
vis[n]=1;
for(int i=0;i<len;i++)
{
int k=son[n][i];
if(vis[k]) continue;
if(k==MAXN[n]){
if(SMAX[k]<SMAX[n]+V[k]){
SMAX[k]=SMAX[n]+V[k];
SMAXN[k]=n;
if(SMAX[k]>MAX[k]){
swap(SMAX[k],MAX[k]);
swap(SMAXN[k],MAXN[k]);
}
}
}
else{
if(SMAX[k]<MAX[n]+V[k]){
SMAX[k]=MAX[n]+V[k];
SMAXN[k]=n;
if(SMAX[k]>MAX[k]){
swap(SMAX[k],MAX[k]);
swap(SMAXN[k],MAXN[k]);
}
}
}
dfs2(k);
}
}
int main()
{
int i,j,k,u,v;
while(scanf("%d",&N)!=EOF)
{
for(i=1;i<=N;i++) son[i].clear();
for(i=2;i<=N;i++){
scanf("%d%d",&u,&V[i]);
son[u].push_back(i); //i的父亲是u
}
memset(vis,0,sizeof(vis));
dfs1(1);
// 测试
// for(i=1;i<=N;i++) printf("~%d ",MAX[i]);printf("\n");
// for(i=1;i<=N;i++) printf("~%d ",SMAX[i]);printf("\n");
memset(vis,0,sizeof(vis));
dfs2(1);
for(i=1;i<=N;i++) printf("%d\n",MAX[i]);
}
return 0;
}
/*
5
1 1
2 1
3 1
1 1
*/
