题解：洛谷 P1351 [NOIP2014 提高组] 联合权值

题目https://www.luogu.com.cn/problem/P1351

我们可以发现，若点对  的距离为 ，则它们一定会经过一个中转点，因此我们考虑枚举中转点 ，然后枚举与  有直接边连接的两个点，按照题意统计答案即可。

#include<bits/stdc++.h>
using namespace std;
#pragma G++ optimisze(3,"Ofast","inline")
#define int long long
const int mod=10007;
int n,a[200005],ans,sum;
vector<int>v[200005];
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int k=1;k<=n;k++){
		for(int i=0;i<v[k].size();i++){
			for(int j=i+1;j<v[k].size();j++){
				ans=max(ans,a[v[k][i]]*a[v[k][j]]);
				sum=(sum+a[v[k][i]]*a[v[k][j]])%mod;
			}
		}
	}
	cout<<ans<<' '<<(sum*2)%mod<<'\n';
	return 0;
}

将代码提交上去，不出意外地超时了（不超时那就有鬼了）。

怎么优化呢？

经过一番冥思苦想，我们发现，树中的最大值乘次大值的值一定是最大的。

问题是总和怎么优化？

看看一个式子：

这就是小学数学中的乘法分配律（千万别跟我说你没学过啊喂）。

设  表示  的子树中的权值值和。

则可以计算出：。

至于最大值和次大值和  可以用 DFS 求出。

实现

#include<bits/stdc++.h>
using namespace std;
#pragma G++ optimisze(3,"Ofast","inline")
#define int long long
const int mod=10007;
int n,a[200005],ans,sum,MAX[200005][2],SUM[200005];
vector<int>v[200005];
void dfs(int x,int fa){
	for(auto z:v[x]){
		SUM[x]+=a[z];
		if(MAX[x][0]<a[z]){
			MAX[x][1]=MAX[x][0];
			MAX[x][0]=a[z];
		}else if(MAX[x][1]<a[z]){
			MAX[x][1]=a[z];
		}
		if(z!=fa){
			dfs(z,x);
		}
	}
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1,x,y;i<n;i++){
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(1,-1);
	for(int k=1;k<=n;k++){
		ans=max(ans,MAX[k][0]*MAX[k][1]);
		for(int i=0;i<v[k].size();i++){
			sum=(sum+a[v[k][i]]*(SUM[k]-a[v[k][i]]))%mod;
		}
	}
	cout<<ans<<' '<<sum<<'\n';
	return 0;
}