DDOSvoid's Blog

Luogu P2325 [SCOI2005]王室联邦

发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P2325

Solution

首先能够发现当 $B\le n$ 时一定有解

我们给出以下这种构造，容易发现一定可以满足 $[B,3B]$ 的条件

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
#include <iostream>
#include <cstdio>
#include <vector>
#define maxn 1010
using namespace std;

int n, B;

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

vector<int> a[maxn]; int ans[maxn], bl[maxn], cnt;
void dfs(int u, int fa) {
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dfs(v, u); for (auto t : a[v]) a[u].push_back(t);
        if (a[u].size() >= B) {
            ans[++cnt] = u;
            for (auto t : a[u]) bl[t] = cnt;
            a[u].clear(); 
        }
    }
    a[u].push_back(u); 
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> B;
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x); 
    } dfs(1, 0);
    if (!cnt) ans[++cnt] = 1; cout << cnt << "\n"; 
    for (auto u : a[1]) bl[u] = cnt; 
    for (int i = 1; i <= n; ++i) cout << bl[i] << " \n"[i == n];
    for (int i = 1; i <= cnt; ++i) cout << ans[i] << " \n"[i == cnt]; 
    return 0;
}