【题解】洛谷 P2296 [NOIP2014 提高组] 寻找道路

题目传送门

题意：

无向连通图 $G$ 有 $n$ 个点，$n-1$ 条边。点从 $1$ 到 $n$ 依次编号,编号为 $i$ 的点的权值为 $W_i$，每条边的长度均为 $1$。图上两点 $(u,v)$ 的距离定义为 $u$ 点到 $v$ 点的最短距离。对于图 $G$ 上的点对 $(u,v)$，若它们的距离为 $2$，则它们之间会产生 $W_u\times W_v$ 的联合权值。

请问图 $G$ 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

题解：

既然“联合”的两个点距离为 $2$，那么它们之间必然有一个中间点。我们可以通过枚举这个中间点来枚举所有的联合距离。

对于一个节点，它的度为 $n$，那么以它为中间点的联合权值的总和 $s$ 为
$$2\sum _{i=1}^{n-1}\sum _{j=i+1}^n{W}_i{W}_j$$
一定要记住，前面有个 $2$，我一开始就是被这个给坑了。

双重和式，硬算复杂度 $O(n^2)$，不 TLE 才怪。
所以我们只好魔改一下这个式子。众所周知：
$$\begin{array}{rl}\frac{1}{2}s& =\sum _{i=1}^{n-1}\sum _{j=i+1}^n{W}_i{W}_j\\ & =W_1{W}_2+W_1{W}_3+...+W_1{W}_n+\\ & W_2{W}_3+W_2{W}_4+...+W_1{W}_n+\\ & ...+\\ & W_{n-1}{W}_n\end{array}$$
然后突然想到了这么一个式子：
$$\begin{array}{rl}(\sum _{i=1}^n{W}_i{)}^2& =W_1^2+W_1{W}_2+...+W_1{W}_n+\\ & W_1{W}_2+W_2^2+...+W_2{W}_n+\\ & ...+\\ & W_1{W}_n+W_2{W}_n+...+W_n^2\end{array}$$
注意到它的主对角线，分别是 $W_1^2$、$W_2^2$、……、$W_n^2$。也就是说，主对角线上的数都是 $W_i^2$ 形式的。再看到主对角线的上下，居然发现各是一个 $\frac{1}{2}s$！所以说，把整个式子减去主对角线上的数的和再除以 $2$ 就可以得到 $\frac{1}{2}s$，再乘回 $2$ 就变成了 $s$。写得学术一点，就是
$$s=(\sum _{i=1}^n{W}_i{)}^2-\sum _{i=1}^n{W}_i^2$$
双重和式就这么被我们拆成了两个单独的和式，计算这个式子的复杂度为 $O(n)$，可以过了。

然后就是最大值的计算。注意不用取模！对于一个中间点，它的最大联合权值就是点权第一大的与点权第二大的乘积。这个很好计算，具体细节参考代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005,inf=0x7fffffff,mod=10007;
vector<int> a[maxn];//邻接表存图
int w[maxn];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(int i=1;i<=n;i++) scanf("%d",&w[i]);
	int tot=0,ans=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i].size()<2) continue;
		int x=0,y=0,maxxx=0,maxx=0;//x计算和的平方，y计算平方的和，maxx是最大的权值，maxxx是第二大的权值
		for(int j=0;j<a[i].size();j++)
		{
			int k=a[i][j];
			x=(x+w[k])%mod;
			y=(y+w[k]*w[k])%mod;
			if(maxx<w[k])//比最大值还大
			{
				maxxx=maxx;//原最大值变成次大值
				maxx=w[k];//最大值更新
			}
			else if(maxxx<w[k]) maxxx=w[k];//直接更新次大值
		}
		tot=(tot+mod+x*x%mod-y)%mod;
		ans=max(ans,maxxx*maxx);
	}
	printf("%d %d",ans,tot%mod);
	return 0;
}