CF2152H1 Victorious Coloring (Easy Version)

线性规划对偶秒了。

由于

q \le 10

，考虑

O(n)

解决单次询问。

首先显然红点形成一个连通块。可以写出线性规划（令

C

表示一个连通块）：

\begin{aligned} \text{minimize}\quad & \sum\limits_{i = 1}^n x_i \\ \text{s.t.}\quad & \forall C, \sum\limits_{(u, v) \in E, u \in C, v \notin C} d_{(u, v)} + \sum\limits_{u \in C} x_u \ge l \\ & x_i \ge 0 \end{aligned}

对偶后有：

\begin{aligned} \text{maximize}\quad & \sum\limits_C y_C (l - \sum\limits_{(u, v) \in E, u \in C, v \notin C} d_{(u, v)}) \\ \text{s.t.}\quad & \forall u, \sum\limits_{u \in C} y_C \le 1 \\ & y_C \ge 0 \end{aligned}

假设

y_C

是整数，那么问题相当于要选出若干个连通块，使得每个点最多被一个连通块包含，且每个选择的连通块

C

都有

l - \sum\limits_{(u, v) \in E, u \in C, v \notin C} d_{(u, v)}

的价值，要求最大化选出的连通块的价值。

考虑树形 DP。设

f_{u, 0/1}

表示

u

是否被一个连通块包含，

u

子树内除了包含

u

的连通块的价值之和的最大值。

转移是简单的。考虑加入一个边权为

d

的儿子

v

：

若 $u, v$ 都没有被连通块包含，则贡献为 $0$ ；
若 $u$ 没有被包含， $v$ 被包含，贡献为 $l - d$ ；
若 $u$ 被包含， $v$ 没有被包含，贡献为 $-d$ ；
若 $u, v$ 都被包含，贡献为 $\max(0, l - 2d)$ ，因为它们可以选择属于同一个连通块或属于不同的连通块。

时间复杂度

O(nq)

。

CPP

// Problem: H1. Victorious Coloring (Easy Version)
// Contest: Codeforces - Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2152/problem/H1
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 250100;

ll n, m, q, f[maxn][2];
vector<pii> G[maxn];

void dfs(int u, int fa) {
	f[u][0] = f[u][1] = 0;
	for (pii p : G[u]) {
		ll v = p.fst, d = p.scd;
		if (v == fa) {
			continue;
		}
		dfs(v, u);
		f[u][0] += max(f[v][0], f[v][1] + m - d);
		f[u][1] += max({f[v][0] - d, f[v][1], f[v][1] + m - d * 2});
	}
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; ++i) {
		vector<pii>().swap(G[i]);
	}
	for (int i = 1, u, v, d; i < n; ++i) {
		scanf("%d%d%d", &u, &v, &d);
		G[u].pb(v, d);
		G[v].pb(u, d);
	}
	scanf("%lld", &q);
	while (q--) {
		scanf("%lld", &m);
		dfs(1, -1);
		printf("%lld\n", max(f[1][0], f[1][1] + m));
	}
}

int main() {
	int T = 1;
	scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

CF2152H1 Victorious Coloring (Easy Version)

文章操作

相关推荐

评论

CF2152H1 Victorious Coloring (Easy Version)