hyz's blog
0%

CF 980E: The Number Games

发表于

题意

给一棵树，节点标记为$1$~$n$，节点$i$的点权为为$2^i$，现在需要删去k个点，使得剩余的点相互联通，且点权的和最大。

分析

看完这道题，首先想到的是贪心，即尽量删去点权小的节点，但是经过仔细思考，容易找到一些反例，因此这个思路是行不通的。这道题的思维难点在于将删去节点转化为选取节点。由数学知识得，$2^{i} = 2^{i-1} + 2^{i-2} + … + 2^{0} + 1 $，所以，我们应该尽量选取标号大的节点。首先，标号为$n$ 的节点是一定可以选取的，把它放到联通块里面，然后我们从大到小，不断往这个联通块添加节点。判断某点能否放进联通块里面，需要看这点与联通块的最短距离是否小于剩余可放的节点数，我们可以使用ST表，在$O(logn)$的时间内来完成。总的时间复杂度就是$O(nlogn)$。

代码

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e6+9;
const int shift=1e3+9;
const double Eps=1e-7;

int u, v, n, k, fa[N][29], vis[N], mm[N];
vi G[N], v1;
set<int> se;

void dfs(int u) {
    vis[u] = 1;
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(vis[v])
            continue;
        fa[v][0] = u;
        dfs(v);
    }
}

void buildST() {
    mm[0] = 0;
    for(int i = 1; i <= n; i++)
        mm[i] = ((i & (i-1)) == 0 ? mm[i-1] + 1 : mm[i-1]);
    for(int j = 1; j <= mm[n]; j++) {
        for(int i = 1; i <= n; i++) {
            if(fa[i][j-1] == -1)
                fa[i][j] = -1;
            else
                fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    cin >> n >> k;
    for(int i = 0; i < n - 1; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(fa, -1, sizeof fa);
    dfs(n);
    buildST();
    k = n - k;
    memset(vis, 0, sizeof vis);
    vis[n] = true;
    v1.push_back(n);
    k--;
    u = n - 1;
    while(k > 0 && u > 0) {
        if(vis[u]) {
            u--;
            continue;
        }
        int t = u, dis = 0;
        for(int i = 20; i >= 0; i--) {
            if(fa[u][i] == -1 || vis[fa[u][i]] == true)
                continue;
            else {
                dis += 1 << i;
                u = fa[u][i];
            }
        }
        u = t;
        dis++;
        if(dis <= k) {
            vis[u] = true;
            v1.push_back(u);
            k--;
            while(vis[fa[u][0]] != true) {
                k--;
                u = fa[u][0];
                vis[u] = true;
                v1.push_back(u);
            }
        }
        u = t - 1;
    }
    for(int i = 1; i <= n; i++)
        se.insert(i);
    for(auto i: v1)
        se.erase(i);
    for(auto i: se)
        printf("%d ", i);
    printf("\n");
    return 0;

}