[树上倍增][贪心][数据性质] codeforces 980E The Number Games

评论区大佬：嗯这个题贪心很明显啦然后nlogn方法也有很多种

http://codeforces.com/contest/980/problem/E

要使得去掉一些点之后剩下的仍然是一棵树，那么去掉的一定是叶子或者某条路上的缩点后相当于叶子的子图。。描述有点困难自行yy。。然后如何选择去掉的点？可以发现，如果i<j，那么去掉j一定不如去掉小于j的所有数，因为2^j=2^(j-1)+2^(j-2)+2^(j-3)+…..+2+1，所以贪心策略就是能不去掉大的就不去，所以要从n-1开始一个一个找（由于k<n所以节点n一定不会被去掉），怎么确定一个点是否能被保留下来，只要确定这个点到最近的保留下来的点的距离小到可以满足去掉k个的要求（想一下，如果这个点离最近的保留点太远了，远到了如果保留这个就没法保证能去掉k个点了，那就肯定不能留了），要保留这个点一定也要保留从这个点往上回溯所有的点，然后就会发现在以root为根的树上，这个01标志是连续的分布的，也就是说有一段1111然后一段000，这样的话就可以二分求分界点，而树上的二分就是lca里的倍增算法了，用倍增法查找就可以在logn时间内找到分界点，找到之后判断是否满足要求，如果满足则把分界点到当前点都标记上保留（话说这样logn不就退化了吗。。。）

wa点是距离的处理和树上倍增往前跳的时候把cur写成了i。。。

#include

using namespace std;
typedef long long LL;
const int maxn=1e6+5e4+5;
const int mod=998244353;
const int INF=0x3f3f3f3f;
const int DG=21;
vector G[maxn];
int dep[maxn],fa[maxn][DG];

void BFS(int root)
{
    queueQ;
    Q.push(root);
    dep[root]=0;
    fa[root][0]=root;//
    int cur,nxt,len;
    while(!Q.empty())
    {
        cur=Q.front();Q.pop();
        for(int i=1;i0&&dis>0;i--)
    {
        if(sav[i])continue;
        cur=i;
        td=0;
        for(int m=DG-1;m>=0;m--)
        {
            if(sav[fa[cur][m]])//error!
                continue;
            cur=fa[cur][m],td+=pow2[m];
        }
        f=fa[cur][0],td++;
        if(td>dis)
            continue;

        dis-=td;
        cur=i;
        while(cur!=f)
        {
            sav[cur]=1;
            cur=fa[cur][0];
        }
    }
    for(int i=1;i<=n;i++)
        if(!sav[i])
        printf("%d ",i);
    return 0;
}
/*

*/