题面
对于一棵有边权的树（N 个结点 N – 1 条边的无向连通图），我们 按以下方法定义其 连通能力：
1、规定某结点的代价为它到其它结点的距离（简单路径所经过边的权值 和）的最大值；
2、代价最小的结点的代价作为这棵树的连通能力。
设某棵给定的树以 1 号结点为根，问以任意结点为根的子树的连 通能力有多大。
分析
太困难了。。
虽然20分送分。
首先看到有关于树上最长链的，能想到树的直径。然而题目中还有一个最小的要求，所以也并不是直径。
不妨将题目要求的东西定义为“树的半径”。因为既在最长链上，但又能保持和两链端的距离大致相等，向左移一步，到右边链端的值会变大，答案也会更大，同理向右移也是。所以在中间位置最优，类似带权中位数，成为既满足最长距离，也满足最小代价。
下面我们来证明这样一个 命题：树的半径一定从树直径的中点两旁的结点到直径的端点处取到。
我们可以尝试使用树形 DP 来解决问题。
在 DFS(u)中，我们需要 以下信息：
1、d(u)表示以 u 为根的子树的直径。
2、mx(u)表示从 u 开始，向深度增大方向的最大路径长度。
3、ed(u）表示使取到 mx(u)的另一个端点
4、dis(u)表示从根到 u 的路径长度。
5、r(u)表示以 u 为根的子树的半径。
注意转移时，我们需要顺便记录从 u 开始，向深度增大方向的次大路径长度。利用孩子结 点的 d、r、ed 我们容易对结点 u 的信息进行第一步维护。唯一没有考虑的情况就是新的 直径由 mx(u)和 mi(u)连接而成。此时我们需要求出这条新直径的中点， 容易看出中点一定在 mx(u)所对应的路径上取到。
求中点的方法有 两种： 一、初始化倍增数组，直接按距离倍增查找，总复杂度 O(Nlog(N)) 二、为每个结点维护 Mid(u)信息，当 mx(u)发生转移时，Mid(u)也随之向深度减小方向转 移。若这样做，总复杂度易证为 O(N)
递归写容易栈溢出，oj上测强行扩栈
代码
#include<bits/stdc++.h> using namespace std; #define N 1000100 inline void read(int &x) { x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=ch-'0'+x*10;ch=getchar();} } int n,cnt; int d[N],dis[N],r[N],mi[N],mx[N],first[N],fa[N],ed1[N],ed2[N]; struct email { int u,v,w; int nxt; }e[N*2]; inline void add(int u,int v,int w) { e[++cnt].nxt=first[u];first[u]=cnt; e[cnt].u=u;e[cnt].v=v;e[cnt].w=w; } void dfs(int u) { mx[u]=mi[u]=d[u]=r[u]=0; ed1[u]=ed2[u]=u; for(int i=first[u];i;i=e[i].nxt) { int v=e[i].v,w=e[i].w; if(v==fa[u])continue; fa[v]=u; dis[v]=dis[u]+w; dfs(v); if(d[v]>d[u]){d[u]=d[v];r[u]=r[v];} if(mx[v]+w>mx[u]) { mi[u]=mx[u];ed2[u]=ed1[u]; mx[u]=mx[v]+w;ed1[u]=ed1[v]; } else { if(mx[v]+w>mi[u]) {mi[u]=mx[v]+w;ed2[u]=ed1[v];} } } if(mx[u]+mi[u]>d[u]) { d[u]=mx[u]+mi[u]; while(ed1[u]!=u&&mi[u]+dis[fa[ed1[u]]]-dis[u]>=(d[u]+1)/2) ed1[u]=fa[ed1[u]]; r[u]=mi[u]+dis[ed1[u]]-dis[u]; if(ed1[u]!=u&&d[u]-mi[u]-(dis[fa[ed1[u]]]-dis[u])<r[u]) r[u]=d[u]-mi[u]-(dis[fa[ed1[u]]]-dis[u]); } } int main() { int siz=40<<20; //__asm__("movl %0, %%esp "::"r"((char*)malloc(siz)+siz));扩栈，调试用,下面一句是提交用。必须exit(0) __asm__ ("movq %0,%%rsp "::"r"((char*)malloc(siz)+siz)); read(n); for(int i=1;i<n;i++) { int u,v,w; read(u);read(v);read(w); add(u,v,w);add(v,u,w); } dis[1]=0;fa[1]=0; dfs(1); for(int i=1;i<=n;i++) printf("%d ",r[i]); exit(0); return 0; }