RT

思路类似 wucstdio 的题解。

#include <bits/stdc++.h>
const int m=10007;
using namespace std;
int n;
vector <int> p[200010];
int w[2000010];
int maxx,maxn,sum1,sum2;
int ans=INT_MAX;
int sum;
void dfs(int x,int fa){
	for(int i=0;i<p[x].size();i++){
		int y=p[x][i];
		if(y!=fa){
			dfs(y,x);
		}
		if(w[y]>maxx){
			maxn=maxx;
			maxx=w[y];
		}
		else if(w[y]>maxn){
			maxn=w[y];
		}
		sum1+=w[y];
		sum1%=m;
		sum2+=w[y]*w[y];
		sum2%=m;
	}
	sum1*=sum1;
	sum1%=m;
	sum+=(sum1-sum2+m)%m;
	ans=min(ans,maxx*maxn);
}
int main(){
	cin>>n;
	for(int i=1;i<=n-1;i++){
		int x,y;
		cin>>x>>y;
		p[x].push_back(y);
		p[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
	dfs(1,20040615+20081210-19950501-20191123);
	cout<<ans<<" "<<sum%m<<endl;
	return 0;
}

调了很久，求助。