自动搬运

查看原文

来自洛谷，原作者为

	wucstdio 这个家伙不懒，但还是什么都没留下

搬运于2025-08-24 21:24:05，当前版本为作者最后更新于2017-10-16 18:05:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神一般的题……

经过了一整天的冥思苦想，终于AC了。

下面是思路：（99.9%都是自己想不出来，老师告诉我的）

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;
}