<题目链接>
题目大意：
输出树上每个点到其它点的最大距离。
解题分析：
下面的做法是将树看成有向图的做法，计算最长路需要考虑几种情况。
dp[i][0] : 表示以i为根的子树中的结点与i的最大距离
dp[i][1] : 表示以i为根的子树中的结点与i的次大距离
dp[i][2] : 表示i往父亲节点方向走的最大距离
第一就是点 i 在以点 i 为根的子树中的最长距离，这个可以直接在点 i 的子树中求得；
第二就是点 i 朝父亲节点方向的最长距离，这个距离分为三种：
1） 点 i 在以 fa 为根的子树中的最长路径上，这时的它朝fa 的最长距离(但是不超过fa的子树继续向上，即只在fa的子树的其它分支进行操作)为 cost<u,fa> + 以fa 为根的子树中的次长路；
2）点 i 不在以fa 为根的子树的最长路径上，这时它朝 fa 的最长距离为(但是不超过fa 的子树继续向上，即只在fa的子树的其它分支进行操作)， cost<u,fa> + fa 子树中的最长路；
3）点 i 向 fa 的 fa 的子树进行扩展比较，所以需要和dp[fa][2] 比较。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int N = 1e4 +;
int dp[N][];
struct Node{
int to,next,cost;
}edge[N]; int n,cnt,head[N];
void init(){
cnt=;
memset(head,-,sizeof(head));
}
void addedge(int u,int v,int w){
edge[cnt].to=v,edge[cnt].cost=w,edge[cnt].next=head[u];
head[u]=cnt++;
}
void dfs1(int u){
int ans1=,ans2=;
for(int i=head[u];~i;i=edge[i].next){
int v=edge[i].to,cost=edge[i].cost;
dfs1(v);
int res=dp[v][]+cost;
if(res>=ans1){
ans2=ans1; //ans1记录最长路,ans2记录次长路
ans1=res;
}else if(res>ans2) ans2=res;
}
dp[u][]=ans1; //dp[u][0]为以u为根的子树的最长路
dp[u][]=ans2; //dp[u][1]为以u为根的子树的次长路
}
void dfs2(int fa){
for(int i=head[fa];~i;i=edge[i].next){
int v=edge[i].to,cost=edge[i].cost;
dp[v][]=max(dp[fa][],dp[v][]+cost == dp[fa][]? dp[fa][]:dp[fa][])+cost;
//dp[fa][2]表示向父亲方向走的最长路; 按v是否在以fa为根的子树中的最长路径上分类讨论，dp[v][2]有两种选择
//相当于，上面的式子考虑了v向fa方向走最长路的三种情况
dfs2(v);
}
}
int main(){
while(~scanf("%d",&n)){
init();
for(int i=;i<=n;i++){
int u,w;scanf("%d%d",&u,&w);
addedge(u,i,w);
}
dfs1();dfs2();
for(int i=;i<=n;i++){
printf("%d\n",max(dp[i][],dp[i][])); //以i为根的最长路;向父亲方向走的最长路
}
}
}
2019-02-03