容易想到贪心,开一个栈,从根开始遍历,每到一个点$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;
}