Description

Input

第一行为N，1<N<=50000,表示树的节点数目，树的节点从1到N编号。

接下来N-1行，每行两个整数U，V，表示U与V之间有一条边。

再接下N行，每行一个正整数，其中第i行的正整数表示编号为i的节点权值为W(I),树的深度<=100

Output

将最小的S（x,y)输出，结果保证不超过19^9

Sample Input

5

1 2

1 3

3 4

3 5

5

7

6

5

4

Sample Output

14

HINT

选取两个中心节点为2,3

—————————————————————————————

这道题很像树的重心只不过这里要求的重心有两个QAQ

考虑树的深度比较小 我们正常求树的重心的方法就是树的高度h

这样算下来我们因为要求两个重心 那么我们可以O（n）枚举一条边把树变成两个

再O（h）算答案 这样复杂度是可以接受的

注意我们本来的sz指的是子树内的权值和

枚举两个点之后两棵树一开始的重心默认为1棵 是1 1棵是u

然后在贪心往下找 

当然这样可能会有问题那就是因为算的是min(dis[x][u],dis[x][v]）

这样的话我们本来是贪心树里面的到这个点 但是这样肯定会错

这样的话其实也影响答案 因为这个只会使当前解比真实解大

最优解的情况是不会受影响的 这样就可以解决这道问题辣

tips sum+=sz[x](x->2-n）

这样其实就是在算路径和 这个转换使代码异常优美2333

#include
       
        #include
        
         #include
         
          #define LL long longusing std::min;using std::swap;const int M=1e5+7;const LL inf=0x3f3f3f3f;char buf[M*33],*ptr=buf-1;int read(){    int ans=0,f=1,c=*++ptr;    while(c<'0'||c>'9'){
     if(c=='-') f=-1; c=*++ptr;}    while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); c=*++ptr;}    return ans*f;}LL ans=inf,sz[M],mx[M],sec[M],sum,w[M];int T,n,fa[M],dep[M];int first[M],cnt;struct node{
     int from,to,next;}e[2*M];void ins(int a,int b){e[++cnt]=(node){a,b,first[a]}; first[a]=cnt;}void insert(int a,int b){ins(a,b); ins(b,a);}void dfs(int x,int f){    sz[x]=w[x]; mx[x]=sec[x]=0;    for(int i=first[x];i;i=e[i].next){        int now=e[i].to;        if(now==f) continue;        fa[now]=x; dep[now]=dep[x]+1;        dfs(now,x); sz[x]+=sz[now];        if(sz[now]>sz[mx[x]]) sec[x]=mx[x],mx[x]=now;        else if(sz[now]>sz[sec[x]]) sec[x]=now;    }}int main(){    fread(buf,1,sizeof(buf),stdin);    int x,y;    n=read();    for(int i=1;i
          
           sz[sec[x]]&&mx[x]!=u) y=mx[x];            else y=sec[x];            if(sz[y]*2>sz[1]) x=y,nowh=nowh-sz[y]*2+sz[1];            else break;        }        x=u;        while(1){            if(sz[mx[x]]*2>sz[u]) nowh=nowh-sz[mx[x]]*2+sz[u],x=mx[x];            else break;        }        ans=min(ans,nowh);        for(x=v;x;x=fa[x]) sz[x]+=sz[u];    }    printf("%lld\n",ans);    return 0;}