支配集

支配集是一种问题：在树上选出若干关键点，使得所有节点到达最近的关键点的距离都不超过 \(k\)。

例题

P3155 [CQOI2009] 叶子的染色

代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 1E4 + 10;

int n, m;
int dp[N][3];

vector<int> adj[N];

void dfs(int u, int f){

    if(u <= n){
        return;
    }
    dp[u][0] = 1;
    dp[u][1] = 1;

    for(auto v : adj[u]){
        if(v == f) continue;
        dfs(v, u);
        dp[u][0] += min(dp[v][0] - 1, min(dp[v][1], dp[v][2]));
        dp[u][1] += min(dp[v][1] - 1, min(dp[v][0], dp[v][2]));
        dp[u][2] += min(dp[v][0], min(dp[v][1], dp[v][2]));
    }

}

int main(){

    cin >> m >> n;
    memset(dp + 1, 0x3f, n * sizeof(int) * 3); //???
    for(int i = 1; i <= n; i++){
        int c;
        cin >> c;
        dp[i][c] = 1;
    }

    for(int i = 1; i <= m - 1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(m, m);

    cout << min(dp[m][0], min(dp[m][1], dp[m][2]));

    return 0;
}