Computer
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 6493 Accepted Submission(s): 3274
Problem Description A school bought the first computer some time ago(so this computer's id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.
Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.
Input Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.
Output For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).
Sample Input
5
1 1
2 1
3 1
1 1
Sample Output
3
2
3
4
4
题目大意：给定一棵树，边有权值，输出离每个结点最远的那个结点的距离。
这题有两种做法，一种就是一般的树形dp，一种利用的是树的直径这个特点，还是按照惯例，先把这两种网上讲的比较好的题解贴出来，然后讲一下我自己的做题感悟
解法一：树形DP
题解1：
从题目可以看出，离第i个结点最远的距离，是边（v,i）的长度（其中v是i 的父亲）加上第v个结点删去i这棵子树之后可以得到的v的最长距离，与i在i的所有子树中可以获得的最大距离 这两者之间的较大值。
用dp[v][0]表示v的孩子最长距离（也就是v在v的所有子树中可以获得的最大距离）
dp[v][1]表示v的孩子第二长距离（这是用来求父亲最长距离的，也就是上述的前者）
dp[v][2]表示v的父亲最长距离（也就是v往上走找最大距离的时候可以获得的最大值）
其中dp[v][0]可以直接通过一次深搜得到，但注意每次搜索的要用一个数组save[v]记录一下，v这个节点的孩子最长距离，经过的第一个孩子就是save[v]
然后再做一次深搜，跳过save[v]就可以得到dp[v][1]了（其实也可以直接记录两组变量得到dp[v][1]，但是感觉这样打得代码没有直接再打一次循环方便。。。但是save[v]还是需要记录的，因为求dp[v][2]的时候要用到）
那么，为什么要记录save[v]呢
首先，我们如果需要求离结点i的最长的结点的距离，而v是i的父亲，假设i往它所有子树走都不是最大距离的时候，那么i的最大距离应该是先往v走一步，然后再求出v的最大距离（而且不能经过i）。
而假如v可以在它的子树中找到最大值时，刚好i又在这条路径里，那么就需要跳过i这条路径，然后看下子树中第二长的路径和v再往v的父亲走一步两者之间的较大值，重复相同过程就可以得到最后的结果。
但是每个节点都这么走一趟的话，时间复杂度会变成n平方。但是可以看出，向上走的距离是可以直接记录下来的，直接深搜一下就可以直接得到了。
那么最后的结果就是 max(dp[i][0],dp[i][2])了
总体时间复杂度（n）
题解2：首先第一个dfs求出所有每个节点i在其子树中的正向最大距离和正向次大距离和dist[i][0]和dist[i][1]（如果i节点在子树中最大距离经过了2号儿子，那么次大距离就是不经过2号儿子的最大距离）。并且还要标记longest[i]=j表示节点i在其子树中的最大距离经过了节点j（即j是i的一个儿子）。
由上步我们获得了正向最大距离，正向次大距离和最大距离的儿子节点标记。画图可以知道我们建立的这棵树，i节点的最远距离只有两种选择：i节点所在子树的最大距离，或者i节点连接它的父节点所能到达的最大距离。（即前者往下走，后者先往上走之后很可能也往下走）
所以我们只要求出反向最大距离dist[i][2]（即i节点往它的父节点走所能到达的最大距离）就可以知道i节点在整个树中能走的最大距离了。
dist[i][2]求法：i节点往它的父节j点走，如果它的父节点的正向最大距离不经过i的话，那么dist[i][2]要不就是它父节点的反向最大距离+W[i][j]要不就是它父节点的正向最大距离+ W[i][j].
如果它的父节点的正向最大距离经过i的话，那么dist[i][2]要不就是它父节点的反向最大距离+W[i][j]要不就是它父节点的正向次大距离+ W[i][j].
小结：
通过这题，又对树这个结构更深的了解了一下，树，他永远只有一个父节点，可能有n个子节点，所以对树种，对于子节点很简单，就是一般的dfs，这时候不要忘记，还有可以先去往一次父节点，这题可以跟子树最大和那题比较下：http://blog.csdn.net/qq_34374664/article/details/55803537，这题是每个点都要求出来，每个点一共3个来源，1从子树来，2先走一步父节点，然后找父节点的子树，3先走一步父节点，然后继续找父节点的父节点。这个是从根节点往下dfs的，你会发现第三个来源，在上面已经都更新完了。子树最大和，只要对结果有正的贡献的都可以加上，而且只是求一个最大和，每个节点的最大和都是由儿子转移过来的，没法走父亲一下，这个要比较下。
代码：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e4 + 5;
vector<int> p[maxn], val[maxn];
int dp[3][maxn], id[maxn];
void dfs1(int x, int f) //第一个dfs更新子树的最大跟次大和
{
for(int i = 0; i < p[x].size(); i++)
{
int to = p[x][i];
if(to == f) continue;
dfs1(to, x);
if(dp[0][x] < dp[0][to] + val[x][i]) //这里是更新最大和，记住经过哪个儿子最大
{
dp[0][x] = dp[0][to] + val[x][i];
id[x] = to;
}
}
for(int i = 0; i < p[x].size(); i++)
{
int to = p[x][i];
if(to == f) continue;
if(id[x] == to) continue; //跳过这个儿子，再剩下点里面找一个最大的，就是这个点次大的
dp[1][x] = max(dp[1][x], dp[0][to]+val[x][i]);
}
}
void dfs2(int x, int f) //这个是更新先往父亲节点走一步的最大和
{
for(int i = 0; i < p[x].size(); i++)
{
int to = p[x][i];
if(to == f) continue;
if(to == id[x]) //难点，每个父亲都有两种方式，一个是再往父亲走一步，一个是走父亲的子树，max(dp[2][x], dp[1][x])，这个就体现出这两部了，注意经不经过这个点直接走子树最大和的那个点
{
dp[2][to] = max(dp[2][x], dp[1][x]) + val[x][i]; //这个是针对儿子，所以是dp[2][to] = ，体现了先走一步父亲，经过就走次大的，再走最大的就重复了一段
}
else
{
dp[2][to] = max(dp[2][x], dp[0][x])+val[x][i];
}
dfs2(to, x); //因为dfs1更新了所有子树的特点，子树的信息可以直接用了，父节点的信息从一步步dfs下去都已经更新好了，上面的也是可以直接用，每一步都看看是不是走父亲的父亲更好，一直更新最优
}
}
int main()
{
int n;
while(~scanf("%d", &n))
{
int a, b;
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++)
{
p[i].clear();
val[i].clear();
}
for(int i = 2; i <= n; i++)
{
scanf("%d%d", &a, &b);
p[i].push_back(a);
val[i].push_back(b);
p[a].push_back(i);
val[a].push_back(b);
}
dfs1(1, -1);
dfs2(1, -1);
for(int i = 1; i <= n; i++)
printf("%d\n", max(dp[0][i], dp[2][i]));
}
return 0;
}
解法二：树的直径
若想做这道题 首先要懂得树的最长路怎么计算
首先假设树的最长路的两个叶子节点为v1,v2，那么现有结论，从任意一点u出发走到的最远的点一定是（v1,v2）中的一点，然后
再从v1或者v2出发走到的最远点一定是v2或者v1。所以经过两次搜索就能找到最长路径。
这里有证明：
假设 s-t这条路径为树的直径，或者称为树上的最长路
现有结论，从任意一点u出发搜到的最远的点一定是s、t中的一点，然后在从这个最远点开始搜，就可以搜到另一个最长路的端点，即用两遍广搜就可以找出树的最长路
证明：
1 设u为s-t路径上的一点，结论显然成立，否则设搜到的最远点为T则
dis(u,T) >dis(u,s) 且 dis(u,T)>dis(u,t) 则最长路不是s-t了，与假设矛盾
2 设u不为s-t路径上的点
首先明确，假如u走到了s-t路径上的一点，那么接下来的路径肯定都在s-t上了，而且终点为s或t，在1中已经证明过了
所以现在又有两种情况了：
1：u走到了s-t路径上的某点，假设为X，最后肯定走到某个端点，假设是t ，则路径总长度为dis(u,X)+dis(X,t)
2：u走到最远点的路径u-T与s-t无交点，则dis(u-T) >dis(u,X)+dis(X,t);显然，如果这个式子成立，
则dis(u,T)+dis(s,X)+dis(u,X)>dis(s,X)+dis(X,t)=dis(s,t)最长路不是s-t矛盾
证明转自 ：http://www.cnblogs.com/*qi/archive/2012/04/08/2437424.html而这道题不是找最长路径，是找某个节点x所能到达的最长路径。首先这个节点x的最长路径要么是到v1的路径，要么就是到v2的路径。由于我们不知道从那边走才是最长的路径 所以需要分别从v1,v2点再次搜索 共需要三次搜索 在这里可能一些同学会说了两次搜索不行吗？我们在第一次搜索找到了v1,v2中的一个点 然后再从v1或者v2点搜索到另外一个点v2或者v1 搜索的过程中用dist[x]保存走过的路径长度 最后输出的时候通过比较当前的路径和最长路径减去到当前的路径 取最大值（max(dist[v]-dist[x],dist[x])） 其实我也是这一些同学的一份子 提交的时候Wa了 后来仔细分析了一下 这样是错误的 我们只能保证x走到的最远点有一点是v1，或者v2 却不能保证另外一点也是 所以不能这样减去。
小结：第一个dfs从任意一个点，随意搜，用一个变量记录距离和最大值，一个变量记录这个点的位置，搜完之后，以那个最大值为起点，再搜一遍就找到了直径的另一个点。这是求直径的方法，正如上面所说的，任何一个点最远的距离，肯定是直径的两个点其中一个，第一遍dfs找出一个直径的点后，用它为起点再dfs一次，两个作用：1找另一个直径的点，2更新所有点到这个点的距离，找到另一个点之后，再来一次，更新到那个点的距离，代码写的很巧妙，仔细学习下
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e4 + 5;
vector<int> p[maxn], val[maxn];
int dp[maxn], max_len, s;
void dfs(int x, int f, int len) //len记录到当前点的距离
{
if(max_len <= len) //max_len记录最长长度，s是寻找直径的两个点，注意要<=
{
s = x;
max_len = len;
}
for(int i = 0; i < p[x].size(); i++)
{
int to = p[x][i];
if(to == f) continue;
dfs(to, x, len+val[x][i]);
dp[to] = max(dp[to], len+val[x][i]); //这里就是更新to这个点到起始点的距离，注意是到起始点的距离，树种两个点的距离是一定的
}
}
int main()
{
int n;
while(~scanf("%d", &n))
{
memset(dp, 0, sizeof(dp));
for(int i = 1;i <= n; i++)
{
p[i].clear();
val[i].clear();
}
int a, b;
for(int i = 2; i <= n; i++)
{
scanf("%d%d", &a, &b);
p[i].push_back(a); //为了不mle，用vect记录长度
val[i].push_back(b);
p[a].push_back(i);
val[a].push_back(b);
}
s = 0;
max_len = 0;
dfs(1, -1, 0); //找第一个点
dfs(s, -1, 0);//找第二个点，更新与第一个的距离
dfs(s, -1, 0); //更新最短距离
for(int i = 1; i <= n; i++)
printf("%d\n", dp[i]);
}
return 0;
}