题目

link

题解

比较简单的做法

访问到每一个节点的时候，在儿子节点中求和，找最大值，次大值来维护答案即可

锅

1.维护sum的时候也要判断if(v == fa) continue

2.不开long long见祖宗

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
int W[N];
int n;
int cnt = 1;
int head[N], nxt[N << 1], to[N << 1];
int maxx = 0, sum = 0;
void add(int x, int y)
{
	to[++cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

void dfs(int u, int fa)
{
	int son_max1 = 0, son_max2 = 0;
	int son_sum = 0;
	for(int i = head[u];i ;i = nxt[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs(v, u);
		son_sum += W[v];
		if(W[v] > son_max1)
		{
			son_max2 = son_max1;
			son_max1 = W[v];
		}
		else if(W[v] > son_max2)
		{
			son_max2 = W[v];
		}
	}
	maxx = max(son_max1 * son_max2, maxx);
	maxx = max(maxx, W[fa] * son_max1);
//	cout << u <<"------" <<endl;
//	cout << son_sum << endl;
	for(int i = head[u]; i ; i = nxt[i])
	{
		if(to[i] == fa) continue;
		int v = to[i];
		sum = (sum + (son_sum - W[v]) * W[v]) % 10007;
	}
	sum = (sum + 2 * W[fa] * son_sum) % 10007;
//	cout << sum << endl;
}


signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1, u, v;i <= n - 1;i++)
	{
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}

	for(int i = 1;i <= n;i++)
		cin >> W[i];

	dfs(1, 0);
	cout << maxx << " " << sum;
	return 0;
}