30分代码求调

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF=114514;
const int maxn=100005;
int n,m,u,v,tot,a[maxn],b[maxn],c[maxn],vis[maxn],rev[maxn],ans[maxn],anc[maxn][20],L[maxn][20],R[maxn][20];

struct query
{
	int type,x,y;
};
query q[maxn];
int lowbit(int i)
{
	return i&-i;
}
void add(int pos,int val)
{
	while (pos<maxn)
	{
		c[pos]+=val;
		pos+=lowbit(pos);
	}
}

int query(int pos)
{
	int res=0;
	while (pos>0)
	{
		res+=c[pos];
		pos-=lowbit(pos);	
	}
	return res;
}
vector<int>G[maxn],nex[maxn];
int dep[maxn],fa[maxn];

void dfs1(int u)
{
	dep[u]=dep[fa[u]]+1;
	anc[u][0]=fa[u];
	for (int i=1;i<20;i++)
	{
		anc[u][i]=anc[anc[u][i-1]][i-1];
	}
	int sz=G[u].size();
	for (int i=0;i<sz;i++)
	{
		int v=G[u][i];
		if (v!=fa[u])
		{
			fa[v]=u;
			dfs1(v);
		}
	}
}

void BFS()
{
	queue<int>Q;
	Q.push(1);
	while (!Q.empty())
	{
		int u=Q.front();Q.pop();
		b[u]=++tot;
		rev[tot]=u;
		int sz=G[u].size();
		for (int i=0;i<sz;i++)
		{
			int v=G[u][i];
			if (v!=fa[u])
			{
				Q.push(v);
			}
		}
		for (int i=0;i<20;i++)
		{
			int v=anc[u][i];
			L[v][i]=min(L[v][i],b[u]);
			R[v][i]=max(R[v][i],b[u]);
		}
	}
}

int getfa(int u,int dis)
{
	int ret=0;
	for (int i=19;i>=0;i--)
	{
		if (ret+(1<<i)<=dis)
		{
			ret+=(1<<i);
			u=anc[u][i];
		}
	}
	return u;
}

int getL(int u,int dis)
{
	int res=0;
	for (int i=19;i>=0;i--)
	{
		if (res+(1<<i)<=dis)
		{
			res+=(1<<i);
			u=rev[L[u][i]];
		}
	}
	return b[u];
}
int getR(int u,int dis)
{
	int res=0;
	for (int i=19;i>=0;i--)
	{
		if (res+(1<<i)<=dis)
		{
			res+=(1<<i);
			u=rev[R[u][i]];
		}
	}
	return b[u];
}
int count(int u,int dis)
{
	if (dis==0)
	{
		return a[u];
	}
	if (dis%2||dep[u]-1<dis/2)
	{
		return 0;
	}
	int f=getfa(u,dis/2-1),v=fa[f];
	int l1=getL(v,dis/2),r1=getR(v,dis/2),l2=getL(f,dis/2-1),r2=getR(f,dis/2-1); 
	return query(l1)-query(l1-1)-query(r2)+query(l2-1);
}
void dfs(int id)
{
	if (id==m+1||vis[id])
	{
		return;
	}
	vis[id]=1;
	if (q[id].type==1)
	{
		int ac=a[q[id].x];
		if (ac)
		{
			add(b[q[id].x],-1);
		}
		else
		{
			add(b[q[id].x],1);
		}
		a[q[id].x]^=1;
		int sz=nex[id].size();
		for (int i=0;i<sz;i++)
		{
			dfs(nex[id][i]);
		}
		dfs(id+1);
		a[q[id].x]=ac;
		add(b[q[id].x],ac==1?1:-1);
	}
	else if (q[id].type==2)
	{
		ans[id]=count(q[id].x,q[id].y);
		int sz=nex[id].size();
		for (int i=0;i<sz;i++)
		{
			dfs(nex[id][i]);
		}
		dfs(id+1);
	}
	else
	{
		int sz=nex[id].size();
		for (int i=0;i<sz;i++)
		{
			dfs(nex[id][i]);
		}
		dfs(id+1);
	}
	
}
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<20;j++)
		{
			L[i][j]=INF;
		}
	}
	for (int i=1;i<n;i++)
	{
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs1(1);
	BFS();
	cin>>m;
	for (int i=1;i<=m;i++)
	{
		cin>>q[i].type>>q[i].x;
		if (q[i].type==2)
		{
			cin>>q[i].y;
		}
		else if (q[i].type==3)
		{
			nex[q[i].x].push_back(i);
		}
	}
	//return 0;
	dfs(0);
	for (int i=1;i<=m;i++)
	{
		if (q[i].type==2)
		{
			cout<<ans[i]<<endl;
		}
	}
}