题意：在一颗树上要求一个到其他结点容量和最大的点，i,j之前的容量定义为i到j的路径上的最小边容量。

一开始想过由小到大的去分割边，但是很难实现，其实换个顺序就很容易做了，类似kruskal的一个贪心算法，

从大到小的连边，每次连通两个分量A和B，这样可以新边容量一定是两个分量相互到达的最小容量，其余边一定选最大，满足最优子结构

而且使新的连通分量取得最大值一定在其中一边，两者中选其中一者即可。具体实现用并查集维护即可。

 

#include
     
      using namespace std;const int maxn = 2e5+5;typedef long long ll;struct node{    int cnt;    ll sum;}town[maxn];int pa[maxn];int Find(int x) { return x==pa[x]?x:pa[x]=Find(pa[x]); }struct Edge{    int u,v,cap;    bool operator < (const Edge &y) const {        return cap > y.cap;    }}road[maxn];#define initNode(x) pa[x] = x; town[x].cnt = 1; town[x].sum = 0;int main(){    //freopen("in.txt","r",stdin);    int n;    while(~scanf("%d",&n)){        for(int i = 1; i < n; i++){            scanf("%d%d%d",&road[i].u,&road[i].v,&road[i].cap);            initNode(i);        }        initNode(n);        sort(road+1,road+n);        for(int i = 1; i < n; i++){            int x = Find(road[i].u), y = Find(road[i].v);            ll t1 = town[x].sum + (ll)town[y].cnt*(ll)road[i].cap;            ll t2 = town[y].sum + (ll)town[x].cnt*(ll)road[i].cap;            if(t1>t2) swap(x,y),swap(t1,t2);            pa[x] = y;            town[y].sum = t2;            town[y].cnt += town[x].cnt;        }        printf("%lld\n",town[Find(1)].sum);    }    return 0;}