题目给一棵树，边带有权值，求每一点到其他点路径上的最大权和。
树上任意两点的路径都可以看成是经过某棵子树根的路径，即路径权=两个点到根路径权的和，于是果断树分治。
对于每次分治的子树，计算其所有结点到根的距离；对于每个结点，找到另一个离根最远的且与该结点路径过根的结点，二者的距离和就是这个点在过这棵子树的根能到的最远距离。
现在问题就是怎么比较快地找到这另一个最远距离的点。。两点路径过根，说明两点间不存在一点是另一点的祖先。。我一开始还想用DFS序+线段树来着。。想了想，想出了线性的算法：
记录每个结点属于根的哪个儿子，把当前分治子树的所有结点以属于根的哪个儿子分组，对于每个结点对应过根的结点就不能在同一组要到别的组找，而且肯定是某个组里面根距离最大的值的那个结点。通过计算每个组里面结点到根的最大值作为组的值，以及这些组的最大值和次大值，就OK了。
好难描述= =反正这样这题就用树分治解决了，时间复杂度O(nlogn)。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF (1<<29)
#define MAXN 33333
struct Edge{
int u,v,w,next;
}edge[MAXN<<];
int NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].u=u; edge[NE].v=v; edge[NE].w=w;
edge[NE].next=head[u]; head[u]=NE++;
} bool vis[MAXN]; int size[MAXN];
void getSize(int u,int fa){
size[u]=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(vis[v] || v==fa) continue;
getSize(v,u);
size[u]+=size[v];
}
}
int centre,mini;
void getCentre(int u,int fa,int &tot){
int res=tot-size[u];
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(vis[v] || v==fa) continue;
getCentre(v,u,tot);
res=max(res,size[v]);
}
if(mini>res){
mini=res;
centre=u;
}
}
int getCentre(int u){
getSize(u,u);
mini=INF;
getCentre(u,u,size[u]);
return centre;
} int n,ans[MAXN];
int dn,dx[MAXN],dy[MAXN],mx1,mx2,belong[MAXN],mx[MAXN];
void dfs(int u,int fa,int dist,int &gp){
dx[dn]=u; dy[dn]=dist; dn++;
belong[u]=gp;
mx[gp]=max(mx[gp],dist);
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(vis[v] || v==fa) continue;
dfs(v,u,dist+edge[i].w,gp);
}
}
void conquer(int u){
dn=; mx1=; mx2=-INF;
dx[dn]=u; dy[dn]=; dn++;
belong[u]=u;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(vis[v]) continue;
mx[v]=-INF;
dfs(v,u,edge[i].w,v);
if(mx1<mx[v]) mx2=mx1,mx1=mx[v];
else if(mx2<mx[v]) mx2=mx[v];
}
for(int i=; i<dn; ++i){
if(mx[belong[dx[i]]]!=mx1) ans[dx[i]]=max(ans[dx[i]],dy[i]+mx1);
else ans[dx[i]]=max(ans[dx[i]],dy[i]+mx2);
}
} void divide(int u){
u=getCentre(u);
vis[u]=;
conquer(u);
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(vis[v]) continue;
divide(v);
}
}
int main(){
int t,a,b,c;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
NE=;
memset(head,-,sizeof(head));
scanf("%d",&n);
for(int i=; i<n; ++i){
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c); addEdge(b,a,c);
}
memset(vis,,sizeof(vis));
for(int i=; i<n; ++i) ans[i]=-INF;
divide();
printf("Case %d:\n",cse);
for(int i=; i<n; ++i) printf("%d\n",ans[i]);
}
return ;
}