困扰了好久了这道题。
这道题我一开始就不懂。
距离为2？一个思路是必定有一个点可以中转！
还有，这道题是一棵树，讨论距离为2的点的可能性：
互为爷孙关系。
互为兄弟关系。
是的，就这两种。
爷孙关系的话，就直接拿它们的权值相乘。两个答案很容易维护。
重点在于兄弟关系。
对于最大值
显然，兄弟中的任意两个都可以构造出答案出来。
那么，答案的最大值应该如何构造？
答案是：最大值和次大值相乘！
如何弄出最大值和次大值出来，可以看代码。我确实不会。
对于和
这个就有点秀了。
设一个点的孩子分别为\(a_1\)，\(a_2\)到\(a_n\)。
有一个神奇的公式：我不知道为什么这么神奇
\[(a_1 + a_2 + ... + a_n)^2 = (a_1^2 + a_2^2 + ... + a_n^2) + 2(a_1 * a_2 + a_1 * a_3 + ... + a_1 * a_n + a_2 * a_3 + ... + a_{n-1} * a_n)\]
这样的话，想要得到这些孩子的联合权值和，只要拿和的平方减掉平方和就可以了。
这个数字刚好是一个一个互相组合得来的和，不知道为什么这么巧。
注意：这个东西不能来统计最大值，这个一求出来就是和的形式。
最后就是：只对和取模，不对最大值取模。
代码：
#include#include const int maxn = 200005, mod = 10007;struct Edges{ int next, to;} e[maxn << 1];int head[maxn], tot;long long w[maxn];int n;long long sum, maxl;void link(int u, int v){ e[++tot] = (Edges){head[u], v}; head[u] = tot;}int read(){ int ans = 0, s = 1; char ch = getchar(); while(ch > '9' || ch < '0') { if(ch == '-') s = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans = ans * 10 + ch - '0'; ch = getchar(); } return s * ans;}void dfs(int u, int fa, int grandfa){ long long maxX = 0, maxx = 0, Sum = 0, squareSum = 0; for(int i = head[u]; i; i = e[i].next) { int v = e[i].to; if(v == fa) continue; dfs(v, u, fa); if(w[v] > maxX)//比最大值还大 { maxx = maxX; maxX = w[v]; } else if(w[v] > maxx) maxx = w[v];//比最大值小，但比次大值大 Sum = (Sum + w[v]) % mod; squareSum = (squareSum + w[v] * w[v]) % mod; } maxl = std::max(maxl, w[u] * w[grandfa]); maxl = std::max(maxl, maxX * maxx); sum = (sum + w[u] * w[grandfa] * 2) % mod; sum = (sum + (Sum * Sum - squareSum)) % mod;}int main(){ n = read(); for(int i = 1; i < n; i++) { int u = read(), v = read(); link(u, v), link(v, u); } for(int i = 1; i <= n; i++) w[i] = read(); dfs(1, 0, 0); printf("%lld %lld\n", maxl, sum % mod); return 0;}
---恢复内容结束---