联合权值

考虑一下，对于一个中节点，他的联合全职是所有临界点*组合的和，也就是a*b+b*c+…..
这个值与a+b+c+。。。。有什么关系呢
2*a*b+2*b*c=(a+b+c+…)^2-a*a+b*b+c*c……
而最大的，是最大值与次大值的组合
所以预处理处所有临界点的和，平方和，最大值次大值就行了O(n)复杂度

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
int n;
const int M=210000;
long long head[M],nex[M*2],to[M*2],tot,ans,w[M],maxx,maxn[M],max2[M],xx[M],yy[M],sum[M],s[M];
void add(int x,int y){
    nex[++tot]=head[x];
    to[tot]=y;
    head[x]=tot;
}

int main(){

    scanf("%d",&n);
    for(int i=1;i<n;i++){

        scanf("%d%d",&xx[i],&yy[i]);

        //add(x[i],y[i]);
        //add(y[i],x[i]);
    }

    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=1;i<=n;i++) {

    }
    for(int i=1;i<=n;i++){
        int x=xx[i],y=yy[i];
        if(w[y]>max2[x]) max2[x]=w[y];
        if(max2[x]>maxn[x]) swap(maxn[x],max2[x]);
        if(w[x]>max2[y]) max2[y]=w[x];
        if(max2[y]>maxn[y]) swap(maxn[y],max2[y]);
        sum[x]+=w[y];
        s[x]+=w[y]*w[y];
        sum[y]+=w[x];
        s[y]+=w[x]*w[x];
    }
    for(int i=1;i<=n;i++) (sum[i]=1ll*sum[i]*sum[i]-s[i])%10007,ans=(ans+sum[i])%10007,maxx=max(maxx,maxn[i]*max2[i]);




    printf("%d %d",maxx,ans);
}