题意：
求树中每个点到所有叶子节点的距离的最大值是多少。
思路：
由于刚学树形dp，就参考了斌巨的博客
连接：http://www.cnblogs.com/kuangbin/archive/2012/08/28/2659915.html
代码：
/* *********************************************** Author :devil Created Time :2016/3/21 15:51:24 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; #define N 10010 int head[N],maxm[N],maxid[N],smaxm[N],smaxid[N],r; struct wq { int v,w,next; } eg[N*2]; void init() { memset(head,-1,sizeof(head)); memset(maxm,0,sizeof(maxm)); memset(smaxm,0,sizeof(smaxm)); r=0; } void add(int u,int v,int w) { eg[r].v=v; eg[r].w=w; eg[r].next=head[u]; head[u]=r++; eg[r].v=u; eg[r].w=w; eg[r].next=head[v]; head[v]=r++; } void dfs1(int u,int fa) { for(int i=head[u]; i!=-1; i=eg[i].next) { int to=eg[i].v; if(to==fa) continue; dfs1(to,u); if(eg[i].w+maxm[to]>smaxm[u]) { smaxm[u]=eg[i].w+maxm[to]; smaxid[u]=to; if(smaxm[u]>maxm[u]) { swap(smaxm[u],maxm[u]); swap(smaxid[u],maxid[u]); } } } } void dfs2(int u,int fa) { for(int i=head[u]; i!=-1; i=eg[i].next) { int to=eg[i].v; if(to==fa) continue; if(to==maxid[u]) { if(eg[i].w+smaxm[u]>smaxm[to]) { smaxm[to]=eg[i].w+smaxm[u]; smaxid[to]=u; if(smaxm[to]>maxm[to]) { swap(smaxm[to],maxm[to]); swap(smaxid[to],maxid[to]); } } } else { if(eg[i].w+maxm[u]>smaxm[to]) { smaxm[to]=eg[i].w+maxm[u]; smaxid[to]=u; if(smaxm[to]>maxm[to]) { swap(smaxm[to],maxm[to]); swap(smaxid[to],maxid[to]); } } } dfs2(to,u); } } int main() { //freopen("in.txt","r",stdin); int n,x,y; while(~scanf("%d",&n)) { init(); for(int i=2; i<=n; i++) { scanf("%d%d",&x,&y); add(i,x,y); } dfs1(1,-1); dfs2(1,-1); for(int i=1;i<=n;i++) printf("%d ",maxm[i]); } return 0; }