n个点，n-1n−1条边，我们很容易就能想到这是一棵树，看数据范围，如果暴力枚举的话，只能拿部分分，这时候我们就回到题目中看，发现，只有距离为22才会产生价值的话，如果枚举一个节点，只有 它和它的孙子之间 或者 它的两个儿子之间 才会产生价值，所以我们就可以枚举这个节点，进行DFSDFS，期间进行更新就好了，具体的实现可以看代码
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <iostream>
5 using namespace std;
6
7 inline int read() {
8 char c = getchar();
9 int x = 0, f = 1;
10 for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
11 for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
12 return x * f;
13 }
14
15 const int N = 1e6 + 11;
16 const int M = 2e5 + 7;
17 const int mod = 10007;
18
19 //邻接表存图
20 struct node {
21 int to, nxt;
22 } e[N];
23
24 int head[M], cnt = 0;
25
26 inline void add(int from, int to) {
27 e[++cnt].to = to;
28 e[cnt].nxt = head[from];
29 head[from] = cnt;
30 }
31
32 int n, w[M], x, y, tot[M], ma[M], cma[M], ans, maxn;
33 //tot[x]数组记录x所有儿子的价值，ma[x]记录x所有儿子中的最大值，cma[x]记录x所有儿子中的次大值
34
35 //DFS!!
36 void dfs(int u, int fa) {
37 //与孙子之间产生的价值
38 for(int i = head[u]; i; i = e[i].nxt) { //枚举儿子节点
39 int v = e[i].to;
40 if(v == fa) continue;
41 dfs(v, u);
42 tot[u] = (tot[u] + w[v]) % mod; //tot[u]加上它儿子v的价值
43 if(w[v] > ma[u]) ma[u] = w[v]; //找它所有儿子的最大值
44 else cma[u] = max(cma[u], w[v]);
45 maxn = max(maxn, w[u] * ma[v]);//答案中的最大值
46 ans = (ans + 2 * w[u] * tot[v] % mod) % mod;//与孙子之间产生的价值（他到他孙子之间的距离一定是2），因为是双向的，所以要乘2
47 }
48 //儿子之间产生的价值
49 for(int i = head[u]; i; i = e[i].nxt) {
50 int v = e[i].to;
51 if(v == fa) continue;
52 if(w[v] == ma[u]) maxn = max(maxn, w[v] * cma[u]); //如果是最大值就与次大值相乘
53 else maxn = max(maxn, w[v] * ma[u]); //否则与最大值相乘
54 ans = (ans + w[v] * (tot[u] - w[v]) % mod) % mod; //其中一个儿子与父节点所有儿子之间产生的价值就是w[v] * (tot[u] - w[v])
55 }
56 }
57
58 int main() {
59 n = read();
60 for(int i = 1; i < n; i++) {
61 x = read(), y = read();
62 add(x, y);
63 add(y, x);
64 }
65 for(int i = 1; i <= n; i++) w[i] = read();//cout << w[i] << '\n';
66 dfs(1, 0);
67 while(ans < 0) ans += mod; //答案可能是负的，只要是负的就一直加模数
68 cout << maxn << " " << ans << '\n';
69 return 0;
70 }