Problem Link

题目大意

给定一棵 $n$ 个点的树，有一些点是黑色，$q$ 次询问 $x$，求最小的 $|S|$，使得将距离 $S$ 中点 $\le x$ 的点全部染黑后，每个点的着色情况恰好和题目给出的一致。

数据范围：$n\le 10^5,q\le 20$。

思路分析

先考虑所有点是黑色的情况。

从最深的点 $u$ 开始考虑，如果 $u$ 还未被覆盖，我们要选一个点既能覆盖 $u$，对外界的影响又尽可能大。

显然考虑 $u$ 的 $x$ 级祖先 $v$，那么 $v$ 子树内的点都会被覆盖，并且对 $v$ 子树外的影响是最大的。

然后考虑一般的情况，设一个点 $u$ 到未被染色的点的距离为 $p_u$，那么我们只选操作 $p_u>x$ 的点。

还是从最深的点 $u$ 开始考虑，那么我们就是要找到一个 $v$ 使得 $\mathrm{dist}(u,v)\le x,p_v>x$ 且 $u$ 尽可能浅。

这样的 $v$ 并不好维护，因为 $v$ 的信息和 $\mathrm{LCA}(u,v)$ 有关。

不妨尝试找最浅的 $w=\mathrm{LCA}(u,v)$，$w$ 固定时，$\mathrm{dist}(v,w)$ 越浅越容易合法，同时此时 $v$ 深度更浅，那么 $v$ 就是子树内最浅的 $p_v>x$ 的 $v$。

那么设 $dis_w$ 表示子树内这样的 $v$ 对应的 $\mathrm{dist}(v,w)$，我们就要求 $dis_w+dep_u-dep_w\le x$ 即 $dep_u\le x+dep_w-dis_w$。

但是此时随着 $w$ 的增加，$dep_w$ 增加，但 $dis_w$ 单调性未知。

但我们发现如果设 $dis_w$ 为所有 $p_v>x$ 的 $v$ 中最小的 $\mathrm{dist}(v,w)$，即去掉子树内限制后，一定有 $|dis_{w}-dis_{fa(w)}|\le 1$.

因此 $w\to fa_w$ 时的变化量一定 $\in[-2,0]$，因此 $x+dep_w-dis_w$ 单调递减，可以倍增出最浅的合法的 $w$。

不难发现此时 $w$ 确实是 $\mathrm{LCA}(u,v)$，因为如果这样的 $v$ 存在，那么 $\mathrm{LCA}(u,v)$ 一定合法，故 $w$ 一定会跳到 $\mathrm{LCA}(u,v)$ 上。

而 $v$ 只要在维护 $dis_w$ 时记录其取值点即可，然后我们要支持覆盖距离 $v$ 不超过 $x$ 的所有点，并查询一个点是否被覆盖，直接点分树维护即可。

时间复杂度 $\mathcal O(nq\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,lim,pri[MAXN],dep[MAXN],dfn[MAXN],dcnt,st[MAXN][20],up[MAXN][20];
char op[MAXN];
vector <int> G[MAXN];
void bfs1() {
	queue <int> q;
	memset(pri,0x3f,sizeof(pri));
	for(int i=1;i<=n;++i) if(op[i]=='0') pri[i]=0,q.push(i);
	while(q.size()) {
		int u=q.front(); q.pop();
		for(int v:G[u]) if(pri[v]>pri[u]+1) q.push(v),pri[v]=pri[u]+1;
	}
}
void dfs0(int u,int fz) {
	dfn[u]=++dcnt,dep[u]=dep[fz]+1,st[dcnt][0]=up[u][0]=fz;
	for(int k=1;k<20;++k) up[u][k]=up[up[u][k-1]][k-1];
	for(int v:G[u]) if(v^fz) dfs0(v,u);
}
int bit(int x) { return 1<<x; }
int cmp(int x,int y) { return dfn[x]<dfn[y]?x:y; }
int dist(int x,int y) {
	if(x==y) return 0;
	int l=min(dfn[x],dfn[y])+1,r=max(dfn[x],dfn[y]),k=__lg(r-l+1);
	return dep[x]+dep[y]-2*dep[cmp(st[l][k],st[r-bit(k)+1][k])];
}
int fa[MAXN],siz[MAXN],cur[MAXN];
bool vis[MAXN];
void dfs1(int u) {
	vis[u]=true;
	function<void(int,int)> dfs2=[&](int x,int fz) {
		siz[x]=1;
		for(int y:G[x]) if(y!=fz&&!vis[y]) dfs2(y,x),siz[x]+=siz[y];
	};
	dfs2(u,0);
	for(int v:G[u]) if(!vis[v]) {
		int rt=0;
		function<void(int,int)> dfs3=[&](int x,int fz) {
			cur[x]=siz[v]-siz[x];
			for(int y:G[x]) if(y!=fz&&!vis[y]) dfs3(y,x),cur[x]=max(cur[x],siz[y]);
			if(!rt||cur[rt]>cur[x]) rt=x;
		};
		dfs3(v,u),fa[rt]=u,dfs1(rt);
	}
}
int d[MAXN],ver[MAXN],rd[MAXN];
void bfs2() {
	queue <int> q; memset(d,0x3f,sizeof(d));
	for(int i=1;i<=n;++i) if(pri[i]>lim) d[i]=0,ver[i]=i,q.push(i);
	while(q.size()) {
		int u=q.front(); q.pop();
		for(int v:G[u]) if(d[v]>d[u]+1) ver[v]=ver[u],d[v]=d[u]+1,q.push(v);
	}
}
void upd(int x) { for(int u=x;u;u=fa[u]) rd[u]=max(rd[u],lim-dist(x,u)); }
bool qry(int x) { for(int u=x;u;u=fa[u]) if(rd[u]>=dist(u,x)) return true; return false; }
vector <int> ord;
void solve() {
	scanf("%d",&lim),bfs2();
	memset(rd,-0x3f,sizeof(rd));
	int ans=0;
	for(int u:ord) {
		if(qry(u)) continue;
		if(d[u]>lim) return puts("-1"),void();
		int v=u;
		for(int k=19;~k;--k) if(up[v][k]&&d[up[v][k]]+dep[u]-dep[up[v][k]]<=lim) v=up[v][k];
		upd(ver[v]),++ans;
	}
	printf("%d\n",ans);
}
signed main() {
	int T;
	scanf("%d%s",&n,op+1);
	for(int i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
	bfs1(),dfs0(1,0);
	for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=n;++i) {
		st[i][k]=cmp(st[i][k-1],st[i+bit(k-1)][k-1]);
	}
	for(int i=1;i<=n;++i) if(op[i]=='1') ord.push_back(i);
	sort(ord.begin(),ord.end(),[&](int x,int y){ return dep[x]>dep[y]; });
	dfs1(1),scanf("%d",&T);
	while(T--) solve();
	return 0;
}

#include<bits/stdc++.h>//by lym
using namespace std;
const int N=1e5+5;
const int inf=1e9;
int a[N];
int n,rt,S;
vector<int>e[N];
int size[N],p[N],tim[N],st[N<<1][20],f[N][20],dep[N],dfn[N],mx[N],b[N],len[N],dis[N],pos[N],id[N];
int lg[N<<1];
int tot=0;
bool vis[N];
void find(int x,int fa){
    size[x]=1;
    mx[x]=0;
    for(int y:e[x]){
        if(vis[y]||y==fa)continue;
        find(y,x);
        size[x]+=size[y];
        mx[x]=max(mx[x],size[y]);
    }
    mx[x]=max(mx[x],S-size[x]);
    if(mx[x]<mx[rt]){
        rt=x;
    }
}
int get(int x,int fa){
    int res=1;
    for(int y:e[x]){
        if(y==fa||vis[y])continue;
        res+=get(y,x);
    }
    return res;
}
void init(int x,int fa){
    dep[x]=dep[fa]+1;
    dfn[x]=++tot;
    f[x][0]=fa;
    st[tot][0]=dep[x];
    for(int i=1;i<=18;i++)f[x][i]=f[f[x][i-1]][i-1];
    for(int y:e[x]){
        if(y==fa)continue;
        init(y,x);
        st[++tot][0]=dep[x];
    }
}
void built(int x){
    vis[x]=1;
    for(int y:e[x]){
        if(vis[y])continue;
        mx[rt=0]=inf;
        S=get(y,x);
        find(y,x);
        p[rt]=x;
        built(rt);
    }
}
int jump(int x,int d){
    for(int i=18;i>=0;i--)if(b[f[x][i]]>=d){
        x=f[x][i];
    }
    return x;
}
int getdis(int x,int y){
    int res=dep[x]+dep[y];
    int xx=x,yy=y;
    x=dfn[x],y=dfn[y];
    if(x>y)swap(x,y);
    int k=lg[y-x+1];
    res-=2*min(st[x][k],st[y-(1<<k)+1][k]);
    if(res==0&&x!=y){
        cout<<"eor"<<endl;
        cout<<xx<<" "<<yy<<" "<<x<<" "<<y<<" "<<k<<endl;
        cout<<dep[xx]<<" "<<dep[yy]<<" "<<st[x][k]<<" "<<st[y-(1<<k)+1][k]<<endl;
    }
    return res;
}
bool check(int x){
    for(int i=x;i;i=p[i]){
        int now=getdis(x,i);
        if(now<=len[i]){
            return 1;
        }
    }
    return 0;
}
void ban(int x,int d){
    for(int i=x;i;i=p[i]){
        int now=d-getdis(x,i);
        if(now>=0)len[i]=max(len[i],now);
        else continue ;
    }
}
bool cmp(int x,int y){
    return dep[x]>dep[y];
}
void solve(int d){
    int ans=0;
    queue<int>q;
    for(int i=1;i<=n;i++)len[i]=dis[i]=-1;
    for(int i=1;i<=n;i++)if(tim[i]>d)q.push(i),pos[i]=i,dis[i]=0;
    if(q.empty()){
        cout<<-1<<endl;
        return ;
    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int y:e[x]){
            if(dis[y]==-1){
                dis[y]=dis[x]+1;
                pos[y]=pos[x];
                q.push(y);
            }
        }
    }
    for(int i=1;i<=n;i++){
        id[i]=i;
        b[i]=dep[i]+d-dis[i];
    }
    sort(id+1,id+1+n,cmp);
    for(int i=1;i<=n;i++){
        int x=id[i];
        if(!a[x]||check(x))continue;
        if(b[x]<dep[x]){
            cout<<-1<<endl;
            return ;
        }
        ans++;
        x=jump(x,dep[x]);
        x=pos[x];
        ban(x,d);
    }
    cout<<ans<<endl;
}
void bfs(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        if(a[i]==0)q.push(i);
        else tim[i]=inf;
    }
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int y:e[x]){
            if(tim[y]==inf){
                tim[y]=tim[x]+1;
                q.push(y);
            }
        }
    }
}
int main(){
    cin>>n;
    mx[0]=inf;
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        a[i]=c-'0';
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    built(1);
    init(1,0);
    bfs();
    for(int i=2;i<=tot;i++){
        lg[i]=lg[i>>1]+1;
    }
    for(int j=1;(1<<j)<=tot;j++){
        for(int i=1;i+(1<<j)-1<=tot;i++){
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        int x;
        cin>>x;
        solve(x);
    }
}