自动搬运

查看原文

来自洛谷，原作者为

	Dilute 为了那个梦我们扬帆启航，只为理应到来的那天跨过无数黑夜。

搬运于2025-08-24 21:43:07，当前版本为作者最后更新于2019-02-21 18:24:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本篇题解讲述的为非完美做法，但是可以骗到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$。

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

• 在$u$节点放一个警探
• 将$u$节点的其中一个警探走向$v$节点（为了防止目标待在$u \rightarrow 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');
    }
}