CF2152H1 Victorious Coloring (Easy Version)

EuphoricStar · 2025-10-10 22:35:07 · 题解

线性规划对偶秒了。

由于 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)。

// 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;
}