算法

(DFS,树的深度优先遍历) $O(N)$

距离为2的点对有两种：

图中实心圆圈表示点对。左边是八字形，右边是1字形。

这两种类型的点对均可在DFS过程中统计。

对于八字形：直接将当前节点的所有子节点两两配对的结果统计出来即可。这一步线性扫描一遍即可，不需要 $O(N^2)$ 枚举。
我们以求总和为例，求最大值类似。从前往后枚举子节点时维护变量 $sum$，表示前面所有子节点的权值和，则每次将 $sum$ 与当前节点的权值的乘积累加起来，就是当前节点的所有子节点两两配对的总权值和。

对于1字形，我们在DFS过程中对每个点维护两个值：f[u]表示节点u的所有子节点权值的最大值，g[u]表示节点u的所有子节点权值之和。那么以u为最高点的1字形点对权值之和就是u的权值乘以u的所有子节点的g[s]之和。求最大值类似。

由于题目中要求的是有序点对的和，因此权值和需要乘2。

时间复杂度

每个节点遍历了一次，因此总时间复杂度是 $O(N)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200010, M = N * 2, mod = 10007;

int n;
int h[N], e[M], ne[M], idx;
int w[N];
int ans_max, ans_sum;
int f[N], g[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u, int father)
{
    int sum = 0, maxv = 0;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j != father)
        {
            dfs(j, u);
            ans_max = max(ans_max, w[u] * f[j]);
            ans_max = max(ans_max, maxv * w[j]);
            maxv = max(maxv, w[j]);
            ans_sum = (ans_sum + w[u] * g[j]) % mod;
            ans_sum = (ans_sum + sum * w[j]) % mod;
            sum = (sum + w[j]) % mod;
            f[u] = max(f[u], w[j]);
            g[u] = (g[u] + w[j]) % mod;
        }
    }
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    dfs(1, -1);
    printf("%d %d\n", ans_max, ans_sum * 2 % mod);

    return 0;
}