题解 CF980E 【The Number Games】
t162
2020-07-10 13:54:05
这题总的来说还是比较套路的。
# 题意理解
给定一颗 $n$ 个结点的无根树，$i$ 号结点权值是 $2^i$ ，求在保证联通的情况下，如何删去 $k$ 个结点使得剩下结点的权值和最大。
# 题解正文
题目让我们求的是删去的结点，我们不妨先求出保留的结点。
容易想到的一个贪心策略是从 $n$ 号结点往 $1$ 号结点贪，能保留的一定保留。
容易证明这个贪心策略是正确的。因为 $2^n>\sum\limits_{i<n}2^i$。
然后我们考虑如何判断一个结点是否能保留。
显然，这个结点到当前已经加入的结点组成的联通块（以下简称`联通块`）的距离如果小于等于还能加入的结点的个数，那么这个结点就能够加入。
那么如何维护某个结点到联通块的距离呢？
树状数组可以做到。
我们要维护的是一些子树内的结点到已经加入的结点组成的联通块的距离。这个操作在基于`DFS序`和`差分`的树状数组上可以很轻松地维护。
实际上新加入的所有结点构成的是一条链。我们只需要暴力跳父亲，直到跳到联通块内的同时对每个子树（除了根在这条链上的）进行维护。
还剩下一个问题，我们贪心的时候要注意当前结点是否已经加入联通块内。
这个问题很好解决，在加入新结点暴力跳父亲时打个标记就行了。
最后输出的时候根据标记输出就好了。
容易证明，这个程序的复杂度是 $O[(n-k)\log n]$。
# 代码
```cpp
//This code was made by Bambusoideae
#include<cstdio>
#include<queue>
#include<vector>
std::vector<int> edge[1000010];
long long tree[1000010];
int begin[1000010],end[1000010],dis[1000010],fix[1000010],vis[1000010],f[1000010],cnt,n,k;
int lowbit(int x){return x&(-x);}
void add(int x,int y){
while(x<=n)tree[x]+=y,x+=lowbit(x);
}
int query(int x){
int ret=0;while(x)ret+=tree[x],x-=lowbit(x);return ret;
}
void dfs(int u,int fa){
begin[u]=++cnt,fix[cnt]=u,f[u]=fa; //算DFS序、距离
for(int i=0;i<edge[u].size();i++){
int v=edge[u][i];
if(v!=fa)dis[v]=dis[u]+1,dfs(v,u);
}
end[u]=cnt;
}
void fil(int x,int l){
add(begin[x],-l),add(end[x]+1,l),vis[x]=1;int last=x;l--;
if(vis[f[x]])return;
for(int i=f[x];!vis[i];last=i,i=f[i],l--)
vis[i]=1, //打标记
add(begin[i],-l),add(end[i]+1,l),
add(begin[last],l),add(end[last]+1,-l); //维护树状数组
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v),edge[u].push_back(v),edge[v].push_back(u);
}
dis[n]=1,dfs(n,0),cnt=0;
k=n-k;add(1,1),vis[0]=1;
for(int i=2;i<=n;i++)add(i,dis[fix[i]]-dis[fix[i-1]]); //建树状数组
for(int i=n;i>0;i--){
if(vis[i])continue;
if(query(begin[i])>k)continue;int l=query(begin[i]);
k-=l,fil(i,l);
}
for(int i=1;i<=n;i++)if(!vis[i])printf("%d ",i);
}
```