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
| int n, b;
vector<int> edge[maxn];
int stk[maxn], tot, bel[maxn], bcnt, key[maxn];
void dfs(int u, int f) {
int bot = tot;
for (int& v: edge[u]) {
if (v == f) continue;
dfs(v, u);
if (tot - bot >= b) {
bcnt++; key[bcnt] = u;
while (tot != bot) {
bel[stk[tot--]] = bcnt;
}
}
}
stk[++tot] = u;
}
int main() {
scanf("%d%d", &n, &b);
for (int i = 2, u, v; i <= n; i++) {
scanf("%d%d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1, 0);
while (tot) bel[stk[tot--]] = bcnt;
printf("%d\n", bcnt);
for (int i = 1; i <= n; i++) printf("%d%c", bel[i], " \n"[i == n]);
for (int i = 1; i <= bcnt; i++) printf("%d%c", key[i], " \n"[i == bcnt]);
return 0;
}
|