洛谷P2325 [SCOI2005]王室联邦

容易想到贪心，开一个栈，从根开始遍历，每到一个点$x$的时候遍历子树，一旦子树内的统计达到$B$了就开一个块，省会设置为$x$，最后遍历完所有点后栈内剩下的点归到最后的一个块内即可

首先整个过程肯定是连续的，$x$的子树内没有分到块内的点可以通过$x$与$x$外相连，所以加上省会的每个块必联通，而一旦遇到$B$就分一个块，所以块大小最大$2B-1$，最后剩下的点肯定也少于$B$，所以最后的一块肯定小于等于$3B-1$，可以保证正确性

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e6 + 10, inf = 0x3f3f3f3f;

const long long Linf = 0x3f3f3f3f3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct EDGE {int u, v, nxt;} edge[N];

int n, B, cnt, head[N], s[N], top, bel[N], rt[N];

void add(int u, int v) {edge[++cnt] = (EDGE){u, v, head[u]}; head[u] = cnt;}

void dfs(int u, int last) {
    int cur = top;
    for (int e = head[u]; e; e = edge[e].nxt) {
        int v = edge[e].v; if (v == last) continue; dfs(v, u);
        if (top - cur >= B) {
            rt[++cnt] = u; while (top > cur) bel[s[top--]] = cnt;
        }
    }
    s[++top] = u;
}

int main() {
    n = read(); B = read();
    for (int i = 1; i < n; i++) {
        int u = read(), v = read(); add(u, v); add(v, u);
    }
    cnt = 0; dfs(1, 0);
    if (!top) rt[++cnt] = 1; while (top) bel[s[top--]] = cnt;
    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++) printf("%d ", bel[i]); printf("\n");
    for (int i = 1; i <= cnt; i++) printf("%d ", rt[i]);
    return 0;
}