真题题解：2014年day1T2 联合权值

思路：

1、联合的两个节点距离为二，所以必定有一个中转点。所以，我们可以枚举每一个中转点。（震惊！！！）

2、假设每个中转点周围有两个点，权值分别为a、b，则联合权值为2ab=(a+b)^2-(a^2+b^2)。

3、若有三个点，权值分别为a、b、c，则联合权值为2ab+2bc+2ac=(a+b+c)^2-(a^2+b^2+c^2)。

4、综上，以某个节点为中转点的联合权值之和等于权值和的平方减去权值的平方和。（+1！！！！！）

5、为了找到最大的联合权值，只需找到周围最大的两个权值max1，max2，相乘判断即可。

注意：虽然题目让%10007，但最大联合权值是不能%10007的！！！（40分WA的看这里！！）

#include<cstdio>
using namespace std;
struct edge
{
    int next;
    int to;
}a[400005];
int edgenum,head[200005],w[200005];
int n,ans,maxx;
void add(int u,int v)//加入一条从u到v的边
{
    a[++edgenum].next=head[u];
    a[edgenum].to=v;
    head[u]=edgenum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)
      scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)
    {
        int max1=0,max2=0;//最大的两个权值
        int t1=0,t2=0;//t1代表和的平方，t2代表平方和
        for(int j=head[i];j;j=a[j].next)
        {
            if(w[a[j].to]>max1)max2=max1,max1=w[a[j].to];
            else if(w[a[j].to]>max2)max2=w[a[j].to];
            t1=(t1+w[a[j].to])%10007;
            t2=(t2+w[a[j].to]*w[a[j].to])%10007;
        }
        t1=t1*t1%10007;
        ans=(ans+t1+10007-t2)%10007;
        if(maxx<max1*max2)maxx=max1*max2;
    }
    printf("%d %d\n",maxx,ans);
    return 0;
}