【题意】给定带点权树，要求选择两个点x,y，满足所有点到这两个点中较近者的距离*点权的和最小。n<=50000,h<=100。

【算法】树的重心

【题解】代码参考自：

观察要求容易发现和重心的定义【所有点距离和最小】十分相似。

要把树分成两部分，于是考虑枚举割掉一条边后，在两棵树中各自找重心。

这样做得到的方案虽然不一定满足题意，但最优解一定在方案中，且不满足题意的方案一定不会比最优解小。

用树形DP求重心，总复杂度O(n^2)。

 

观察到最大深度<=100，可以用【往子树权和>sum/2的子树走】的方法求解。

这种做法的正确性：设当前点为重心的答案是ans，则往子树走ans=ans-sum[son]+(sum-sum[son])=ans+sum-2*sum[son]，由此可知当sum[son]>sum/2时对答案有贡献。

理解做法后，关键在如何简洁的实现。

对每个点计算size，mx（最大儿子），mx2（次大儿子）。mx只记编号。

计算初始重心答案：s+=size[x],x=2~n。（这里技巧性很强，将所有size都加一次，最底端自然累计了路径数）

枚举边u-v，将边上端v到根的size修改，sum=s后修改sum（这里用sum减去路径数次的size[u]，这样就是初始双中心设在1和u了）。

然后从初始双重心往下找重心即可，记得一部分sum是sum[1]，另一部分sum是sum[u]。

整个过程的答案只需要：ans+=sum-2*sum[son]。

#include
      
       #include
       
        #include
        
         #define ll long longusing namespace std;const int maxn=50010;const ll inf=1ll<<60;int fa[maxn],deep[maxn],tot,first[maxn],mx[maxn],mx2[maxn],n,w[maxn];ll ans,size[maxn];struct edge{
    int u,v,from;}e[maxn*3];void insert(int u,int v){tot++;e[tot].u=u;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}void dfs(int x,int f){    size[x]=w[x];mx[x]=mx2[x]=0;    for(int i=first[x];i;i=e[i].from)if(e[i].v!=f){        deep[e[i].v]=deep[x]+1;        fa[e[i].v]=x;        dfs(e[i].v,x);        size[x]+=size[e[i].v];        if(size[e[i].v]>size[mx[x]]){mx2[x]=mx[x];mx[x]=e[i].v;}        else if(size[e[i].v]>size[mx2[x]])mx2[x]=e[i].v;    }}int main(){    scanf("%d",&n);    int u,v;    memset(first,0,sizeof(first));    tot=0;    for(int i=1;i
         
          size[mx2[x]]&&mx[x]!=u)y=mx[x];else y=mx2[x];            if(size[y]*2>size[1])sum+=size[1]-2*size[y],x=y;else break;        }        x=u;        while(1){            if(size[mx[x]]*2>size[u])sum+=size[u]-2*size[mx[x]],x=mx[x];else break;        }        ans=min(ans,sum);        for(int x=v;x;x=fa[x])size[x]+=size[u];    }    printf("%lld",ans);    return 0;}