Codeforces 980E(倍增)

发表于 | 分类于 | | + s

Codeforces 980E
题意：有一颗无根树编号$1$到$n$，每个点权值为$2^i$, 要删除$k$个点，并且删后原树还是联通的。请问整棵树权值最大的删点方案？

因为每个点权值为$2^i​$，而$2^i = \sum_{j=1}^{i-1}2^j+1​$，所以最大的那个点权值比其他所有点的权值都大。那么我们必须用一切代价保留大编号的点。我们可以把删除转化为选择问题，看从大开始能选几个点进去。预处理将$n​$转为根，$n​$加入选择集合。这个选择集合的所有节点必须在树上是连通块。所以我们枚举$n-1​$到$1​$的点看它到联通块的最短距离来判断能不能加，能加就把路径上所有点加入集合。对于看它到联通块集合的最短距离，我们用树上倍增的方法找到距离该点最近的已经在联通块集合的点在哪里。

易错点：
1、$10^5~10^6$以上要输入输出优化
知识点：
1、$2^i = \sum_{j=1}^{i-1}2^j+1$
2、删除转化为选择问题
3、将$n$转为根：不一定要用$1$当根

Codeforces Submission

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1e6 + 5, logs = 20;
int n, k, vis[MAXN], pre[MAXN][logs + 5];
vector<int> G[MAXN];
inline void ins(int x, int y) {
    G[x].push_back(y), G[y].push_back(x);
}
void dfs(int u, int pa) {
    pre[u][0] = pa;
    for (int i = 1; i <= logs; i++) pre[u][i] = pre[pre[u][i - 1]][i - 1];
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];
        if (v != pa) dfs(v, u);
    }
}
void clean() {
    ms(vis, 0), ms(pre, 0);
}
int solve() {
    clean();
    cin >> n >> k; 
    if (n == k) {for (int i = 1; i <= n; i++) printf("%d\n", i); return 0;}
    k = n - k - 1;
    for (int x, y, i = 1; i < n; i++) scanf("%d%d", &x, &y), ins(x, y);
    dfs(n, 0), vis[n] = 1;
    for (int x = n - 1; x; x--) {
        int t = k, v = x, flag = 0;
        for (int i = logs; i >= 0; i--) {
            if (vis[v]) {flag = 1; break;}
            if (pre[v][i] == 0) continue;
            if (t < (1 << i)) continue;
            v = pre[v][i], t -= (1 << i);
        }
        if (vis[v]) flag = 1;
        v = x;
        if (flag) {
            while (!vis[v]) {
                vis[v] = 1, k--;
                v = pre[v][0];
            }
        }
        if (k == 0) break;
    }
    for (int i = 1; i <= n; i++) if (!vis[i]) printf("%d\n", i);
    return 0; 
}
int main() {
    solve();
    return 0;
}
//23:11-23:19-23:23-23:29
//¿ªÊ¼Ð´´úÂë-´úÂëÍê³É-¾²Ì¬µ÷ÊÔÍê³É-¹ýÑùÀý
------ 本文结束 ------