『贪心·树上倍增』CF980E The Number Games

题目描述

题解

观察题目性质，每一个节点的权值都是2的整次幂，性质为：$$2^k>\sum _{i=1}^{k?1}{2}^i$$

这意味着我们需要优先选择大的。

从大到小枚举每一个节点，如果没有被选取就将它到根路径的每一个点都赋值为$1$.

观察一下这样的性质，发现：某一个点被覆盖，其到根路径上的所有点也会被覆盖。

因此，我们用树上倍增查找，不断朝上向根节点跳跃，若被标记，则不跳；否则跳跃并记录路经长度。

由于每一个点都会被覆盖一次，所以只要部分的时间复杂度是$O(n)$的，但是基于倍增，复杂度变成了$O(nlogn)$

#include <bits/stdc++.h>using namespace std;
const int N = 1e6+10;int n, k;
int f[N][21], vis[N];vector <int> a[N];void dfs(int x,int fa)
{
    for (int i=0;i<a[x].size();++i){
    int y = a[x][i];if (y == fa) continue;f[y][0] = x;dfs(y,x);}return;
}void dp(void)
{
    for (int j=1;j<=20;++j)for (int i=1;i<=n;++i)f[i][j] = f[f[i][j-1]][j-1];return;
}int find(int x)
{
    int sum = 0;for (int i=20;i>=0;--i)if (!vis[f[x][i]])  sum += (1<<i), x = f[x][i];return sum+1;
}int main(void)
{
    scanf("%d %d", &n, &k), k = n-k;for (int i=1,x,y;i<n;++i){
    scanf("%d %d", &x, &y);a[x].push_back(y);a[y].push_back(x);}dfs(n,0);vis[0] = 1, dp();for (int i=n;k>0;--i){
    if (vis[i] == 1) continue;int no_tag = find(i), now = i;if (no_tag > k) continue;while (vis[now] == 0) k --, vis[now] = 1, now = f[now][0];} for (int i=1;i<=n;++i)if (vis[i] == 0) printf("%d ", i);return 0;
}