主页
归档
朋友
关于

题解P2892 追捕盗贼

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

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

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

算了反正我也看不懂

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

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

预处理

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

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

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

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

构造方案

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

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

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

  • 在uu节点放一个警探
  • 将uu节点的其中一个警探走向vv节点（为了防止目标待在u→vu \rightarrow v的边上赖着不走）
  • 递归做vv节点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#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');
    }
}

QQ

|

Codeforces

|

Luogu

|

Github
本站由 Hexo 驱动，使用 Azurus 作为主题。