描述

无向连通图 G 有 n 个点，n-1 条边。点从 1 到 n 依次编号，编号为 i 的点的权值为 WiWi， 每条边的长度均为 1。图上两点(u, v)的距离定义为 u 点到 v 点的最短距离。对于图 G 上的点对(u, v)，若它们的距离为 2，则它们之间会产生WuWu×WvWv的联合权值。

请问图 G 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

格式

输入格式

第一行包含 1 个整数 n。

接下来 n-1 行，每行包含 2 个用空格隔开的正整数 u、v，表示编号为 u 和编号为 v 的点 之间有边相连。

最后 1 行，包含 n 个正整数，每两个正整数之间用一个空格隔开，其中第 i 个整数表示 图 G 上编号为 i 的点的权值为WiWi。

输出格式

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

样例1

样例输入1[复制]

5

1 2

2 3

3 4

4 5

1 5 2 3 10

样例输出1[复制]

20 74

限制

对于 30%的数据，1 < n ≤ 100；

对于 60%的数据，1 < n ≤ 2000；

对于 100%的数据，1 < n ≤ 200,000，0 < WiWi ≤ 10,000。

【题解】





设w[a]+w[b]+w[c]+w[d]=sum[e]

则这个图的答案就是w[a](sum[e]-w[a])+w[b](sum[e]-w[b])+….

这样只要枚举n-1条边就能算出总的权值了;

最大权值只要求出和上图中c相邻的点中w的值最大和次大的就好;

要求出每个点的次大和最大;

然后取它们乘积的最大值;

#include <cstdio>

#include <cmath>

#include <set>

#include <map>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <stack>

#include <string>

#define lson L,m,rt<<1

#define rson m+1,R,rt<<1|1

#define LL long long

using namespace std;

const int MAXN = 2e5+100;

const int MOD = 10007;

const int dx[5] = {0,1,-1,0,0};

const int dy[5] = {0,0,0,-1,1};

const double pi = acos(-1.0);

struct bian

{

    int x,y;

};

struct abc

{

    int max1,max2;

};

int n;

bian b[MAXN];

int w[MAXN],sum[MAXN];

abc c[MAXN];

void input_LL(LL &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)) t = getchar();

    LL sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

void input_int(int &r)

{

    r = 0;

    char t = getchar();

    while (!isdigit(t)) t = getchar();

    int sign = 1;

    if (t == '-')sign = -1;

    while (!isdigit(t)) t = getchar();

    while (isdigit(t)) r = r * 10 + t - '0', t = getchar();

    r = r*sign;

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    input_int(n);

    for (int i = 1;i <= n-1;i++)

        input_int(b[i].x),input_int(b[i].y);

    for (int i = 1;i <= n;i++)

        input_int(w[i]);

    for (int i = 1;i <= n-1;i++)

    {

        int x = b[i].x,y = b[i].y;

        sum[x]=(sum[x]+w[y])%MOD;

        sum[y]=(sum[y]+w[x])%MOD;

        if (w[y]>c[x].max1)

        {

            swap(c[x].max1,c[x].max2);

            c[x].max1 = w[y];

        }

        else

            if (w[y]>c[x].max2)

                c[x].max2 = w[y];

        if (w[x]>c[y].max1)

        {

            swap(c[y].max1,c[y].max2);

            c[y].max1 = w[x];

        }

        else

            if (w[x]>c[y].max2)

                c[y].max2 = w[x];

    }

    int ans1 = c[1].max1*c[1].max2;

    for (int i = 2;i <= n;i++)

        if (c[i].max1*c[i].max2>ans1)

            ans1 = c[i].max1*c[i].max2;

    int ans2 = 0;

    for (int i = 1;i <= n-1;i++)

    {

        int x = b[i].x,y = b[i].y;

        ans2 = (ans2+w[y]*(sum[x]-w[y]+MOD) + MOD)%MOD;

        ans2 = (ans2+w[x]*(sum[y]-w[x]+MOD) + MOD)%MOD;

    }

    printf("%d %d\n",ans1,ans2);

    return 0;

}