\(>Codeforces \space 980 E. The Number Games<\)
题目大意 : 有一棵点数为 \(n\) 的数，第 \(i\) 个点的点权是 \(2^i\) 你需要删掉 \(k\) 个点，使得删掉这些点后树依然联通，且剩下的点权之和最大，并输出方案
\(n , k \leq 10^6\)
解题思路 :
问题可以转化为选取 \(n - k\) 个点，使得选取的点联通且权值和最大
根据点权是 \(2^i\) 的性质，显然有选取编号为 \(x\) 的点比选取 \(i = [1, x)\) 之间的所有点还要优
首先 \(n\) 一定要保留，于是可以将 \(n\) 设置为 \(root\) 把无根树变成有根树来简化问题
接下来不妨贪心的从大到小保留点，因为点权都是 \(2^i\) 所以一个点如果能选取就必然会被选取
考虑如果要选取一个点必然要选取他的所有祖先，所以一个点能否被选取取决于其到 \(root\) 的
路径上没有被选取的点的个数
所以对于一个点 \(x\) 只需要倍增找到其到 \(root\) 路径上最深的已经被选取的点 \(y\)
那么路径上没有被选取的点的个数就是 \(dep_x - dep_y\)，如果可以选取就暴力选取这些点
因为每个点只会被最多选取一次，所以复杂度得以保证，总复杂度是 \(O(nlogn)\)
/*program by mangoyang*/
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define N (1000005)
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int f = 0, ch = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
vector<int> g[N];
int f[N][24], dep[N], ff[N], n, k;
inline void dfs(int u, int fa){
dep[u] = dep[fa] + 1, f[u][0] = fa;
for(int i = 0; i < g[u].size(); i++){
int v = g[u][i];
if(v != fa) dfs(v, u);
}
}
inline int get(int x){
for(int i = 22; i >= 0; i--)
if(!ff[f[x][i]] && f[x][i]) x = f[x][i];
return x;
}
int main(){
read(n), read(k), k = n - k;
for(int i = 1, x, y; i < n; i++){
read(x), read(y);
g[x].push_back(y), g[y].push_back(x);
}
dfs(n, 0);
for(int j = 1; j <= 22; j++)
for(int i = 1; i <= n; i++)
f[i][j] = f[f[i][j-1]][j-1];
for(int i = n; i >= 1; i--) if(!ff[i]){
int u = i, ls = get(u);
if(dep[u] - dep[ls] + 1 <= k)
k -= dep[u] - dep[ls] + 1; else continue;
for(int s = u; s != ls; s = f[s][0]) ff[s] = 1;
ff[ls] = 1;
if(!k) break;
}
for(int i = 1; i <= n; i++)
if(!ff[i]) printf("%d ", i);
return 0;
}