QTREE6树链剖分

QTREE6.cpp

#include <cstdio>
#include <algorithm>
const int N = 200009;
int col[N],c[N * 2],In[N],Ou[N],f[N][20],tot[N],d[N],top[N],Max[N],rt[N],sz[N],n,n2,m,lc[N * 2],rc[N * 2],add[N * 2][2],cnt,t[N];
int L,R,V,son[N],lnk[N * 2],nxt[N * 2],ec;
inline void addedge(const int x,const int y)
{
	nxt[++ec] = son[x];
	son[x] = ec;
	lnk[ec] = y;
}
inline void Addedge(const int x,const int y){addedge(x,y);addedge(y,x);}
int Count(int x)
{
	int res = 0;
	for (; x; x -= x & -x) res += c[x];
	return res;
}
void update(int x,const int delta)
{
	for (; x <= n2; x += x & -x) c[x] += delta;
}
int get(int u)
{
	for (int i = 19,fa; i >= 0; --i)
		if ((fa = f[u][i]) && Count(In[u]) - Count(In[f[fa][0]]) == (d[u] - d[fa] + 1) * col[u])
			u = fa;
	return u;
}
int query(const int idx,const int l,const int r,const int x,const int flag)
{
	if (!idx) return 0;
	if (l == r) return add[idx][flag];
	const int mid = (l + r) / 2;
	if (x <= mid) return add[idx][flag] + query(lc[idx],l,mid,x,flag);
	else return add[idx][flag] + query(rc[idx],mid + 1,r,x,flag);
}
void modify(int &idx,const int l,const int r,const int flag)
{
	if (!idx) idx = ++cnt;
	if (L <= l && r <= R) return(void)(add[idx][flag] += V);
	const int mid = (l + r) / 2;
	if (L <= mid) modify(lc[idx],l,mid,flag);
	if (mid < R) modify(rc[idx],mid + 1,r,flag);
}
void M(int &root,const int l,const int r,const int flag)
{
	L = d[l] - d[top[l]] + 1;
	R = d[r] - d[top[r]] + 1;
	modify(root,1,tot[top[l]],flag);
}
void modify(int u,int v,const int flag)
{
	while (top[u] != top[v]) {
		if (d[top[u]] < d[top[v]]) std::swap(u,v);
		M(rt[u],top[u],u,flag);
		u = f[top[u]][0];
	}
	if (d[u] < d[v]) std::swap(u,v);
	M(rt[u],v,u,flag);
}
inline int Q(const int u,const int flag)
{
	if (!flag) return query(rt[u],1,tot[top[u]],d[u] - d[top[u]] + 1,flag) + sz[u];
	else return query(rt[u],1,tot[top[u]],d[u] - d[top[u]] + 1,flag) + 1; 
}
int query(int u)
{
	u = get(u);
	return Q(u,col[u]);
}
void modify(const int u)
{
	int v = get(u);
	V = -Q(u,col[v]);
	if (u != 1) modify(f[u][0],(f[v][0] ? f[v][0] : v),col[v]);
	int NEW = (col[u] ^ 1);
	update(In[u],NEW - col[u]);
	update(Ou[u],col[u] - NEW);
	col[u] = NEW;
	v = get(u);
	V = Q(u,col[v]);
	if (u != 1) modify(f[u][0],(f[v][0] ? f[v][0] : v),col[v]);
}
void build(int x)
{
	int tp = x;
	rt[tp] = ++cnt;
	for (; x; x = Max[x]) rt[x] = rt[top[x] = tp],++tot[tp];
}
void dfs()
{
	sz[Max[0] = N -  1] = 0x3f3f3f3f;
	int nodes = 0;
	d[1] = 1;
	for (int p = 1; p; ) {
		if (!In[p]) In[p] = ++nodes;
		if (son[p]) {
			if (lnk[son[p]] == f[p][0]) {
				son[p] = nxt[son[p]];
				continue;
			}
			d[lnk[son[p]]] = d[p] + 1;
			f[lnk[son[p]]][0] = p;
			int t = son[p];
			son[p] = nxt[son[p]];
			p = lnk[t];continue;
		}
		sz[f[p][0]] += (++sz[p]);
		if (sz[Max[f[p][0]]] > sz[p]) build(p);
		else {
			if (Max[f[p][0]]) build(Max[f[p][0]]);
			Max[f[p][0]] = p;
		}
		Ou[p] = ++nodes;
		p = f[p][0];
	}
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("QTREE6.in","r",stdin);
	freopen("QTREE6.out","w",stdout);
	#endif
	scanf("%d",&n);
	n2 = n + n;
	for (int i = 1,x,y; i < n; ++i) {
		scanf("%d%d",&x,&y);
		Addedge(x,y);
	}
	dfs();
	for (int i = 1; i < 20; ++i)
		for (int j = 1; j <= n; ++j)
			f[j][i] = f[f[j][i - 1]][i - 1];
	scanf("%d",&m);
	for (int x,y; m--; ) {
		scanf("%d%d",&x,&y);
		if (x == 0) printf("%d\n",query(y));
		else modify(y);
	}
}