CF208E Blood Cousins【线段树合并】

传送门
之前用 dsu on tree 搞过一次，这次试着用线段树合并来做，尝试了一下内存回收，基本可以把空间压到 (O(n))。不错不错。
把询问用向前星来存，速度和空间都比用 vector 存好一些。
这道题的做法也是先把询问离线，然后每个点建以深度为权值的线段树，先 dfs，然后回溯的时候合并子树的线段树，再查每个点的问题。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,dep[N],m,fa[N][22],ans[N],rt[N];
int head[N],to[N*2],nxt[N*2],tot;
void add(int u,int v) {to[++tot]=v;nxt[tot]=head[u];head[u]=tot;}
int qhead[N],qto[N*2],qnxt[N*2],qid[N*2],qtot;
void qadd(int u,int v,int id) {qto[++qtot]=v;qid[qtot]=id;qnxt[qtot]=qhead[u];qhead[u]=qtot;}
int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	return x*f;
}
struct SegTrees{
	#define mid (l+r>>1)
	queue<int> que;
	int sum[N*20],ls[N*20],rs[N*20],tot;
	int newnode(){if(que.empty()) return ++tot;int u=que.front();que.pop();return u;}
	void delnode(int id){que.push(id);sum[id]=ls[id]=rs[id]=0;}
	void upd(int &id,int l,int r,int pos){
		if(!id) id=newnode();
		if(l==r) {sum[id]++;return;}
		if(pos<=mid) upd(ls[id],l,mid,pos);
		else upd(rs[id],mid+1,r,pos);
		sum[id]=sum[ls[id]]+sum[rs[id]];
	}
	void merge(int &x,int y,int l,int r){
		if(!x||!y) {x=x+y;return;}
		if(l==r) {sum[x]+=sum[y];delnode(y);return;}
		merge(ls[x],ls[y],l,mid);
		merge(rs[x],rs[y],mid+1,r);
		sum[x]=sum[ls[x]]+sum[rs[x]];
		delnode(y);
	}
	int ask(int id,int l,int r,int pos){
		if(!id) return 0;
		if(l==r) return sum[id];
		if(pos<=mid) return ask(ls[id],l,mid,pos);
		else return ask(rs[id],mid+1,r,pos);
	}
	#undef mid
}trs;

void predfs(int u,int rt){
	dep[u]=dep[rt]+1;fa[u][0]=rt;
	for(int i=head[u];i;i=nxt[i]) if(to[i]!=rt) predfs(to[i],u);
}

void dfs(int u,int fa){
	trs.upd(rt[u],1,n,dep[u]);
	for(int i=head[u];i;i=nxt[i]){
		if(to[i]==fa) continue;
		dfs(to[i],u);
		trs.merge(rt[u],rt[to[i]],1,n);
	}
	for(int i=qhead[u];i;i=qnxt[i])
		ans[qid[i]]=trs.ask(rt[u],1,n,qto[i]);
}

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		int u=read();
		add(u,i);add(i,u);
	}
	for(int i=head[0];i;i=nxt[i]) predfs(to[i],0);
	for(int i=1;i<=20;i++) for(int j=1;j<=n;j++) fa[j][i]=fa[fa[j][i-1]][i-1];
	m=read();
	for(int i=1;i<=m;i++){
		int u=read(),k=read(),rt=u,temp=k;
		for(int j=20;j>=0;j--) if(k>=(1<<j)) rt=fa[rt][j],k-=(1<<j);
		if(rt==0) continue;
		qadd(rt,temp+dep[rt],i);
	}
	for(int i=head[0];i;i=nxt[i]) dfs(to[i],0);
	for(int i=1;i<=m;i++) printf("%d ",ans[i]?ans[i]-1:0);
	return 0;
}