自动搬运

查看原文

来自洛谷，原作者为

	bluewindde d2673e765642345244b4fb8edf1add1cf8425a4b7743f39b020d410d67ce15b0

搬运于2025-08-24 23:06:35，当前版本为作者最后更新于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();
}