(>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;
}