The Number Games(DFS序+树状数组)

描述

传送门:Codeforces Round #480 (Div. 2) - Problem E

The nation of Panel holds an annual show called The Number Games, where each district in the nation will be represented by one contestant.

The nation has $n$ districts numbered from $1$ to $n$, each district has exactly one path connecting it to every other district. The number of fans of a contestant from district $i$ is equal to $2^i$.

This year, the president decided to reduce the costs. He wants to remove $k$ contestants from the games. However, the districts of the removed contestants will be furious and will not allow anyone to cross through their districts.

The president wants to ensure that all remaining contestants are from districts that can be reached from one another. He also wishes to maximize the total number of fans of the participating contestants.

Which contestants should the president remove?

Input

The first line of input contains two integers $n$ and $k$ ($1 ≤ k < n ≤ 10 ^ 6$) the number of districts in Panel, and the number of contestants the president wishes to remove, respectively.

The next $n-1$ lines each contains two integers $a$ and $$ ($1≤a,b≤n$, $a≠b$), that describe a road that connects two different districts $a$ and $b$ in the nation. It is guaranteed that there is exactly one path between every two districts.

Output

Print $k$ space-separated integers: the numbers of the districts of which the contestants should be removed, in increasing order of district number.

Example

Input Output
1
2
3
4
5
6
6 3
2 1
2 6
4 2
5 6
2 3
1
1 3 4
1
2
3
4
5
6
7
8
8 4
2 6
2 7
7 8
1 2
3 1
2 4
7 5
1
1 3 4 5

Note

In the first sample, the maximum possible total number of fans is $2 ^ 2 + 2 ^ 5 + 2 ^ 6 = 100$. We can achieve it by removing the contestants of the districts $1$, $3$, and $4$.

思路

  • 题意:一棵有$n$个点的树,每个点的权值为$2^i$。现在要求去掉$k$个点,剩余的点保持连通的情况下,权值最大。
  • 一个比较显然的结论是:$2 ^ n > \sum\limits_{i=0} ^ {n - 1}{2 ^ i}$,也就是说,我们要尽可能的留下编号较大的点。
  • 于是可以考虑从第$n$个点开始贪心,为了保持连通性,我们取第$i$个点,就要将它与要保留的点集的路径上的点都要保留,如果需要保留的结点加上已经保留的结点超过了$n-k$,那就不能保留。
  • 那么现在的问题就是要处理如何维护一个点到要保留的点集的路径上的结点个数。
  • 在最开始,每个点到$n$的路径上的结点个数就是深度,而每次选择一个点,那么这条路径上每个点的子树上的每个点都会少一个这样的点,在dfs序下就是一个区间更新。拿数据结构维护一下就好了。

代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
using namespace std;
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define X first
#define Y second
#define fastin \
ios_base::sync_with_stdio(0); \
cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-6;

struct BIT
{
const static int N = 1 << 20;
int a[N];
BIT() { clr(a, 0); }
void update(int x, int v)
{
for (int i = x; i < N; i+= i & -i) a[i] += v;
}
int query(int x)
{
int t = 0;
for (int i = x; i; i -= i & -i) t += a[i];
return t;
}
} t;

vector<vector<int> > G;
vector<int> fa;
vector<int> in, out;
int dfn;
void dfs(int u, int p, int d)
{
fa[u] = p, in[u] = ++dfn;
t.update(in[u], d), t.update(in[u] + 1, -d);
for (auto& v : G[u])
if (v != p) dfs(v, u, d + 1);
out[u] = dfn;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
fastin
int n, k;
cin >> n >> k;
dfn = 0;
G.resize(n + 1);
fa.resize(n + 1);
in.resize(n + 1);
out.resize(n + 1);
for (int i = 1, u, v; i < n; i++)
{
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(n, -1, 1);
vector<bool> vis(n + 1);
for (int i = n, cnt = 0; i; i--)
{
if (vis[i]) continue;
int len = t.query(in[i]);
if (cnt + len <= n - k)
{
for (int u = i; ~u && !vis[u]; u = fa[u])
{
vis[u] = true, cnt++;
t.update(in[u], -1), t.update(out[u] + 1, 1);
}
}
}
for (int i = 1; i <= n; i++)
if (!vis[i]) cout << i << " ";
return 0;
}
捐助作者
0%