题目大意：
每台新电脑都与某一台原电脑相连有一个长度，求每台电脑相距其最远的电脑的距离
这里因为第一台电脑是最初的，所以可以将第一台电脑作为树根，其他电脑分布就可以形成一棵树
这里距离有两种，一种是往树底找，一种是往父节点方向走
第一次dfs记录下每个节点往子节点方向找到其树底的最长距离，第二次dfs记录每个节点如果一开始往父节点方向走所能得到的最大距离
最后判断两者中得到一个最大值就行了
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int N = 10005; 7 8 int first[N] , maxn[N][4] , k , vis[N]; 9 /*10 maxn[i][0] 表示i往下到其树底的最长距离，11 maxn[i][1]表示到树底的次长距离，12 maxn[i][2]表示i节点往上寻找到的最长距离13 最后只要比较判断往上找还是往下找能得到的最大距离即可14 */15 struct Edge{16 int y , next , d;17 }e[N<<1];18 19 void add_edge(int x , int y , int d)20 {21 e[k].y = y , e[k].d = d , e[k].next = first[x];22 first[x] = k++;23 }24 25 void my_swap(int &x , int &y)26 {27 int temp = x;28 x = y , y = temp;29 }30 31 void dfs1(int u)32 {33 vis[u] = 1;34 for(int i = first[u] ; i!=-1 ; i=e[i].next){35 int v = e[i].y;36 if(!vis[v]){37 dfs1(v);38 //更新次长和最长值,自底向上更新，所以写在dfs后面进行回溯39 if(maxn[u][1] < maxn[v][0] + e[i].d){40 maxn[u][1] = maxn[v][0] + e[i].d;41 if(maxn[u][0] < maxn[u][1])42 my_swap(maxn[u][0] , maxn[u][1]);43 }44 }45 }46 }47 48 void dfs2(int u)49 {50 vis[u] = 1;51 for(int i= first[u] ; i!=-1 ; i=e[i].next){52 int v = e[i].y;53 if(!vis[v]){54 //自顶向下更新，所以写在dfs前面55 //判断是否最大值落于当前分支56 int tmp;57 if(maxn[u][0] - maxn[v][0] == e[i].d)58 tmp = maxn[u][1];59 else tmp = maxn[u][0];60 maxn[v][2] = max(maxn[u][2] , tmp) + e[i].d;61 dfs2(v);62 }63 }64 }65 66 int main()67 {68 // freopen("a.in" , "r" , stdin);69 int n , d , a;70 while(scanf("%d" , &n) == 1)71 {72 k = 0;73 memset(first , -1 , sizeof(first));74 for(int i=2 ; i<=n ; i++){75 scanf("%d%d" , &a , &d);76 add_edge(a , i , d);77 add_edge(i , a , d);78 }79 80 memset(maxn , 0 , sizeof(maxn));81 memset(vis , 0 , sizeof(vis));82 dfs1(1);83 84 memset(vis , 0 , sizeof(vis));85 dfs2(1);86 /*87 for(int i=1 ; i<=n ; i++)88 printf("%d %d %d\n" , maxn[i][0] , maxn[i][1] , maxn[i][2]);89 */90 for(int i=1 ; i<=n ; i++)91 printf("%d\n" , max(maxn[i][0] , maxn[i][2]));92 }93 return 0;94 }