算法知识点: DFS，树的深度优先遍历

复杂度：

解题思路：

距离为2的点对有两种：八字形和1字形。

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

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

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

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


另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ