消除死域点题解

对于每一个点，考虑把它删除后，从 死域点 变成 非死域点 的只可能是它的祖先，且 具有 单调性，所以考虑遍历一遍树，把祖先用 vector 存储，再去二分，故复杂度 $O(nlogn)O(n\; log\; n)$ ，可以通过本题。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+100;
int n,k;
int sz[maxn];
int ans;
vector<int> edge[maxn];
vector<int> chifan;
void dfs1(int now,int fa){
	sz[now]++;
	for(int i=0;i<edge[now].size();i++){
		if(edge[now][i]!=fa){
			dfs1(edge[now][i],now);
			sz[now]+=sz[edge[now][i]];
		}
	}
}
void dfs2(int u,int f){
	if(sz[u] >= k) chifan.push_back(u);
    for(int v : edge[u]) {
        if(v == f) continue;
        dfs2(v, u);
    }
    if(sz[u] >= k) chifan.pop_back();
    int l = -1, r = chifan.size(), mid;
    while(l + 1 < r) {
        mid = (l + r) / 2;
        if(sz[chifan[mid]] - sz[u] >= k) l = mid;
        else r = mid;
    }
    /*[u1 u2 [u3 ux]]*/
    ans = max(ans, (int)chifan.size() - r);
}
int sum;
int main(){
	cin>>n>>k;
	k++;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs1(1,0);
	for(int i=1;i<=n;i++){
		if(sz[i]>=k){
			sum++;
		}
	}
	dfs2(1,0);
	cout<<sum-ans;
}