洛谷P1351 联合权值(树形dp)

时间：2024-10-09 08:07:07

题意

题目链接

Sol

一道很简单的树形dp，然而被我写的这么长

分别记录下距离为\(1/2\)的点数，权值和，最大值。以及相邻儿子之间的贡献。

树形dp一波。。

#include<bits/stdc++.h>

#define Fin(x) {freopen(x, "r", stdin);}

#define int long long

using namespace std;

const int MAXN = 2e5 + 10, mod = 10007;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, a[MAXN];

vector<int> v[MAXN];

int f[MAXN][3], sum[MAXN][3], num[MAXN][3],  dis[MAXN], down[MAXN], Son[MAXN];

int add(int x, int y) {

	if(x + y < 0) return x + y + mod;

	else return x + y >= mod ? x + y - mod : x + y;

}

int mul(int x, int y) {

	return 1ll * x * y % mod;

}

void dfs(int x, int fa) {

	dis[x] = 0;

	for(int i = 0, to; i < v[x].size(); i++) {

		if((to = v[x][i]) == fa) continue;

		dfs(to, x);

		dis[x] = add(dis[x], mul(sum[x][1], a[to]));

		if(!Son[x]) Son[x] = a[to];

		else down[x] = max(down[x], a[to] * Son[x]), Son[x] = max(Son[x], a[to]);

		f[x][1] = max(f[x][1], a[to]);

		f[x][2] = max(f[x][2], f[to][1]);

		sum[x][1] = add(sum[x][1], a[to]);

		sum[x][2] = add(sum[x][2], sum[to][1]);

		num[x][1]++;

		num[x][2] += num[to][1];

	}

}

signed main() {

	memset(f, -1, sizeof(f));

	N = read();

	for(int i = 1; i <= N - 1; i++) {

		int x = read(), y = read();

		v[x].push_back(y); v[y].push_back(x);

	}

	for(int i = 1; i <= N; i++) a[i] = read();

	dfs(1, 0);

	int mx = 0, s = 0;

	for(int i = 1; i <= N; i++) {

		if(~f[i][2]) mx = max(mx, a[i] * f[i][2]);

		if(num[i][2]) s = add(s, mul(a[i], sum[i][2]));

		if(num[i][1] > 1) s = add(s, dis[i]), mx = max(mx, down[i]);

	}

	cout << mx << " " << s * 2 % mod;

	return 0;

}

/*

*/

相关文章