题解 P2892 【[NOI2007]追捕盗贼】

· · 题解

本篇题解讲述的为非完美做法，但是可以骗到96分

\huge\text{在本人blog食用更佳}

说实话我在网上找了好久结果都是这个O(n^2)的非正解树型DP

听说有个O(N)的正解在某篇论文里？

算了反正我也看不懂

所以我接下来就介绍一下这个O(n^2)的树型DP吧QwQ

顺手丢一下我学习的这篇blog吧

预处理

首先我们先用f[i]表示占领以i为根的子树所需要的人数

然后我们可以很显然地列出一个方程f[u] = \max\{f[v]\}

然后我们还要特判一下，如果有多个f[v] = max\{f[v]\}，那么得f[u]得再加上1

因为在我们进行每一个子树的占领的时候除了最后一个，必须得有一个人待在root处（具体可以看后面的代码）

构造方案

首先，我们预处理n次，分别以1~n为根，接下来就可以确定一个答案最小的根。

确认根之后，我们显然要先向根丢一个人，然后以为前面所说，我们得先把f[v]不是最大的v给先处理掉，然后再做f[v]最大的v。

而我们访问一棵子树的顺序如下：

代码

#include<bits/stdc++.h>

#define ll long long
#define INF 2147483647

inline int inp(){
    char c = getchar();
    while(c < '0' || c > '9')
        c = getchar();
    int sum = 0;
    while(c >= '0' && c <= '9'){
        sum = sum * 10 + c - '0';
        c = getchar();
    }
    return sum;
}

int head[100010];
int nxt[20010];
int end[20010];
char type[100000];
int num1[100000], num2[100000];
int cnt = 0;
int cou = 0;
int f[20010];

void link(int a, int b){
    nxt[++cou] = head[a];
    head[a] = cou;
    end[cou] = b;
}

void dfs(int cur, int last){
    int max = 0;
    bool mt = true;
    for(int x = head[cur]; x != -1; x = nxt[x]){
        if(end[x] != last){
            dfs(end[x], cur);
            if(f[end[x]] > max){
                max = f[end[x]];
                mt = false;
            } else if(f[end[x]] == max)
                mt = true;
        }
    }
    if(mt)
        f[cur] = max + 1;
    else
        f[cur] = max;
}

void dfs2(int cur, int last){
    int max = 0;
    bool mt = true;
    int degree = 0;
    int pos;
    for(int x = head[cur]; x != -1; x = nxt[x]){
        if(end[x] != last){
            dfs(end[x], cur);
            if(f[end[x]] > max){
                max = f[end[x]];
                mt = false;
                pos = end[x];
            } else if(f[end[x]] == max)
                mt = true;
            degree++;
        }
    }
    // printf("%d %d pos = %d\n", cur, last, pos);
    if(degree == 0){
        type[++cnt] = 'B';
        num1[cnt] = cur;
        return ;
    }
    for(int x = head[cur]; x != -1; x = nxt[x]){
        if(end[x] != pos && end[x] != last){
            type[++cnt] = 'L';
            num1[cnt] = cur;
            type[++cnt] = 'M';
            num1[cnt] = cur;
            num2[cnt] = end[x];
            dfs2(end[x], cur);
        }
    }
    type[++cnt] = 'M';
    num1[cnt] = cur;
    num2[cnt] = pos;
    dfs2(pos, cur);
    if(mt)
        f[cur] = max + 1;
    else
        f[cur] = max;
}

int main(){
    memset(head, -1, sizeof(head));
    int n = inp();
    for(int i = 1; i < n; i++){
        int u = inp();
        int v = inp();
        link(u, v);
        link(v, u);
    }
    int root = 0;
    int min = INF;
    for(int i = 1; i <= n; i++){
        dfs(i, 0);
        if(f[i] < min){
            min = f[i];
            root = i;
        }
    }
    dfs2(root, 0);
    printf("%d\n%d\n", min, cnt + 1);
    printf("L %d\n", root);
    for(int i = 1; i <= cnt; i++){
        putchar(type[i]);
        printf(" %d", num1[i]);
        if(type[i] == 'M')
            printf(" %d", num2[i]);
        putchar('\n');
    }
}