第一反应是树形dp，讨论兄弟和爷爷两种情况。想了想觉得不够优雅就去看了题解…
优雅的做法是枚举中间点！
设当前点为x，x所连的点为(a,b,c,...)
对于求最大值，只要每次记录x连接的最大的两个点，并检查更新答案即可。
因为求有序点对，所以(a,b)(b,a)都会被算一次。
那么x的最终贡献即为$2ab+2ac+2bc+...$
它等价于$(a+b+c+...)^2 - (a^2+b^2+c^2...)$
注意：取模的时候因为有减法，必须保证答案为正数。
代码如下
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define MogeKo qwq using namespace std; const int maxn = 4e5+10; const int mod = 10007; int n,x,y,m1,m2,s1,s2; int w[maxn],head[maxn],to[maxn],nxt[maxn]; int M,ans,cnt; void add(int x,int y) { to[++cnt] = y; nxt[cnt] = head[x]; head[x] = cnt; } int main() { scanf("%d",&n); for(int i = 1; i <= n-1; i++) { scanf("%d%d",&x,&y); add(x,y),add(y,x); } for(int i = 1; i <= n; i++) scanf("%d",&w[i]); for(int k = 1; k <= n; k++) { m1 = m2 = s1 = s2 = 0; for(int i = head[k]; i; i = nxt[i]) { int v = to[i]; if(w[v] > m1) { m2 = m1; m1 = w[v]; } else if(w[v] > m2) m2 = w[v]; s1 = (s1 + w[v]) %mod; s2 = (s2 + w[v]*w[v]) %mod; } M = max(M,m1*m2); ans = (ans + (s1*s1%mod) %mod - s2 + mod)%mod; } printf("%d %d",M,ans); return 0; }
原文：https://www.cnblogs.com/mogeko/p/11635526.html
