NOIP2014提高组.联合权值

题目

511. 联合权值

算法标签: 树上问题, $dfs$, 前缀和

思路

因为考虑路径长度为$2$的点对$(u,v)$, 可以将该点对分为两类, 分别统计最大值

可以固定第一条边, 枚举下一条边的选法

在求总和的规程中, 可以维护一个前缀和, 在计算当前子节点$v$来说直接乘前缀和时间复杂度是$O(n)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 200010, M = N << 1, MOD = 10007;

int n;
int w[N];
int head[N], ed[M], ne[M], idx;
int max_ans, sum_ans;

void add(int u, int v) {
   
	ed[idx] = v, ne[idx] = head[u], head[u] = idx++;
}

void dfs(int u, int fa) {
   
	int max_val = 0, sum = 0;
	for (int i = head[u]; ~i; i = ne[i]) {
   
		int v = ed[i];
		if (v == fa) continue;
		if (fa != -1) {
   
			max_ans = max(max_ans, w[fa] * w[v]);
			sum_ans = (sum_ans + w[fa] * w[v] % MOD) % MOD;
		}
		max_ans = max(max_ans, (int) (LL) max_val * w[v]);
		sum_ans = (sum_ans + sum * w[v] % MOD) % MOD;
		max_val = max(max_val, w[v]);
		sum = (sum + w[v]) % MOD;
		dfs(v, u);
	}
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);

	cin >> n;
	for (int i = 0; i < n - 1; ++i) {
   
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	for (int i = 1; i <= n; ++i) cin >> w[i];

	dfs(1, -1);

	cout << max_ans << " " << sum_ans * 2 % MOD << "\n";
	return 0;
}