P11342 [KTSC 2023 R1] 外环道路 2 题解

bluewindde · 2025-04-21 17:27:33 · 题解

考虑二分图染色，一条连接同色点的边会产生代价，所以 DP 最优染色方案。

设 dp_{u, 0 / 1, 0 / 1, 0 / 1} 表示 u 子树内，根节点颜色为 0 / 1，最左边的叶子颜色为 0 / 1，最右边的叶子颜色为 0 / 1 的最小代价。后三个状态压成二进制 S。这里先不考虑连接 V[n] 和 V[1] 的外环边，最后答案为 \min\limits_S dp_{1, S} + [S[0] = S[1]] \cdot W[k]。

合并子树时枚举 u 子树的状态 S 和 v 子树的状态 T。如果 S 和 T 的根节点颜色相同，则连接这两个点的边需要产生代价；如果 S 最右边的叶子颜色和 T 最左边的叶子颜色相同，则连接这两个点的外环边需要产生代价。

边界：对于叶子，dp_{u, 0} = dp_{u, 7} = 0；对于非叶子，初始状态需要直接继承其一个儿子。时间复杂度 O(n)。

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

namespace sol {

#define int long long

const int inf = 1e18;

static inline void chkmin(int &x, int y) {
    if (x > y)
        x = y;
}

int n, k;
int a[100005];
vector<pair<int, int>> vec[100005];

int dfn[100005], dfn_clock;
int low[100005];
int dp[100005][2][8];
static inline int dfs(int u) {
    if (vec[u].empty()) {
        dp[u][0][0] = dp[u][0][7] = 0;
        return ++dfn_clock;
    }
    int x;
    {
        int v = vec[u][0].first, w = vec[u][0].second;
        x = dfs(v);
        for (int S = 0; S < 8; ++S) {
            chkmin(dp[u][0][S], dp[v][0][S] + w);
            chkmin(dp[u][0][S ^ 4], dp[v][0][S]);
        }
    }
    for (int i = 1; i < (int)vec[u].size(); ++i) {
        memset(dp[u][i & 1], 0x3f, sizeof dp[u][i & 1]);
        int v = vec[u][i].first, w = vec[u][i].second;
        int o = dfs(v);
        for (int S = 0; S < 8; ++S)
            for (int T = 0; T < 8; ++T)
                chkmin(dp[u][i & 1][(S ^ (S & 1)) | (T & 1)], dp[u][(i - 1) & 1][S] + dp[v][0][T] + (((S >> 2) & 1) == ((T >> 2) & 1) ? w : 0) + ((S & 1) == ((T >> 1) & 1) ? a[x] : 0));
        x = o;
    }
    if (!(vec[u].size() & 1))
        memcpy(dp[u][0], dp[u][1], sizeof dp[u][0]);
    return dfn_clock;
}

static inline int solve() {
    memset(dp, 0x3f, sizeof dp);
    dfs(1);
    int ans = inf;
    for (int S = 0; S < 8; ++S)
        chkmin(ans, dp[1][0][S] + (((S >> 1) & 1) == (S & 1) ? a[k] : 0));
    return ans;
}

#undef int

} // namespace sol

long long place_police(vector<int> P, vector<long long> C, vector<long long> W) {
    int n = sol::n = (int)P.size() + 1, k = sol::k = (int)W.size();
    for (int i = 0; i < n - 1; ++i)
        sol::vec[P[i] + 1].push_back({i + 2, C[i]});
    for (int i = 0; i < k; ++i)
        sol::a[i + 1] = W[i];
    return sol::solve();
}