题目描述

无向连通图G有n个点，n-1条边。点从1到n依次编号，编号为i的点的权值为Wi ，每条边的长度均为1。图上两点(u, v)的距离定义为u点到v点的最短距离。对于图G上的点对(u, v)，若它们的距离为2，则它们之间会产生Wu×Wv的联合权值。请问图G上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

输入描述:

第一行包含1个整数n。
接下来n-1行，每行包含2个用空格隔开的正整数u、v，表示编号为u和编号为v的点之间有边相连。
最后1行，包含n个正整数，每两个正整数之间用一个空格隔开，其中第i个整数表示图G上编号为i的点的权值为。

输出描述:

输出共1行，包含2个整数，之间用一个空格隔开，依次为图G上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对10007取余。

示例1

输入
5
1 2
2 3
3 4
4 5
1 5 2 3 10
输出
20 74
说明

本例输入的图如上所示，距离为2的有序点对有(1,3)、(2,4)、(3,1)、(3,5)、(4,2)、(5,3)。其联合权值分别为2、15、2、20、15、20。其中最大的是20，总和为74。

备注

对于30%的数据，1＜n ≤ 100；
对于60%的数据，1＜n ≤ 2000；
对于100%的数据，1＜n ≤ 200000，0＜Wi ≤ 10000。
保证一定存在可产生联合权值的有序点对。

解答

首先不难看出如果要求联合权值和必须枚举所有能产生联合权值的情况。又因为产生联合权值的两点u,v中间肯定间隔一点i，并且我们发现如果以u或v为起点枚举情况的话其效率是很低的。因此我们需要枚举i。

对i来说，所有与它相连的点中的任意两点都会产生联合权值。那么我们就可以通过枚举所有与他相连的点。但此做法的时间复杂度为n方，是我们不能接收的。所以我们需要找规律。

设与i相连的点编号分别为1、2、3……，点1的权为w1，那么所产生的联合权值S为，化简得同时；所以我们只需要统计点1、2、3、4的权的和sum和权的平方和sumn，i点所连的点产生的联合权值Si=sum-sumn；最后求S的和即为联合权值的总和。

对于最大值，我们只需要记住与i相连的点中权的最大和次大值，乘积即为i相连的点中最大的联合权值Maxi。

最后枚举i，在所有Maxi取最大即为最大联合权值。

PS：只需对和取模。

代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 200050;
long long a[MAXN][4];
int b[MAXN][2];
long long pos[MAXN];
int main()
{
    int n;
    int i,j;
    int x,y;
    long long sum,sumn,summ;
    long long maxn;
    long long fx,fy;
    memset(a,0,sizeof(a)); 
    scanf("%d",&n);
    for(i=1;i<n;i++)
    {
        scanf("%d%d",&b[i][0],&b[i][1]);
    }
    for(i=1;i<=n;i++)
    {
        scanf("%d",&pos[i]);
    }    
    for(i=1;i<n;i++)
    {    
        x=b[i][0];
        y=b[i][1];    
        fx=pos[x];
        fy=pos[y];
        a[x][0]+=fy;
        a[y][0]+=fx;
        a[x][1]+=fy*fy;
        a[y][1]+=fx*fx;
        if(fy>a[x][2])
        {
            a[x][3]=a[x][2];
            a[x][2]=fy;
        }
        else if(fy>a[x][3])
        {
            a[x][3]=fy;
        }
        if(fx>a[y][2])
        {
            a[y][3]=a[y][2];
            a[y][2]=fx;
        }
        else if(fx>a[y][3])
        {
            a[y][3]=fx;
        }
    }
    sum=0;
    sumn=0;summ=0;
    maxn=0;
    for(i=1;i<=n;i++)
    {
        summ=(a[i][0]*a[i][0]-a[i][1]);
        sum+=summ;
        sum=sum % 10007;
        sumn=a[i][2]*a[i][3];
        if(sumn>maxn)
        {
            maxn=sumn;
        }
    }
    printf("%lld %lld",maxn,sum);
    return 0;
}



来源：Macwyw