【树链剖分+二分】Query on a tree VI

二分, 树状数组, 树链剖分

传送门：CodeChef-QTREE6

题意：给定一棵树，开始时每个点是黑色的，要求支持单点翻转颜色，询问同色连通块大小

思路：

对一棵树进行树链剖分，维护以每个点在其子树中的连通块大小，可用树状数组分别维护黑白2色

那么询问时只需跳到同色连通块顶部

对于重链，维护点权和（黑为1，白为0），然后可以快速判断一段链上是否是一个颜色

不是就二分

维护连通块是区间修改单点查询

维护区间和是单点修改区间查询

可以用3个树状数组来维护

注意：

注意跳重链时不要重复，对于根节点有一些特判，否则可能会重复

二分以后：r!=dfn[cur]

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 600000
int n,m,x,y,op,tot,clk,xb,tmp,fa[N],deep[N],size[N],head[N],top[N],dfn[N],bit[3][N],col[N];
struct edge{int v,nxt;}e[N];
void addedge(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void dfs1(int cur){
	if (!fa[cur]) fa[cur]=cur; deep[cur]=deep[fa[cur]]+1; size[cur]=1;
	for (int i=head[cur];i;i=e[i].nxt)
		if (fa[cur]!=e[i].v){fa[e[i].v]=cur; dfs1(e[i].v); size[cur]+=size[e[i].v];};
}
void dfs2(int cur){
	if (!top[cur]) top[cur]=cur; dfn[cur]=++clk;
	int t=0;
	for (int i=head[cur];i;i=e[i].nxt) if (fa[cur]!=e[i].v && size[e[i].v]>t) t=e[i].v;
	if (!t) return; top[t]=top[cur]; dfs2(t);
	for (int i=head[cur];i;i=e[i].nxt) if (fa[cur]!=e[i].v && e[i].v!=t) dfs2(e[i].v);
}
void add(int op,int x,int k){for (int i=x;i<=n;i+=i&(-i)) bit[op][i]+=k;}
void ins(int op,int l,int r,int k){
	if (op==0 || op==1){add(op,l,k); add(op,r+1,-k);}
	if (op==2) add(op,l,k);
}
int ask(int op,int x){int sum=0; for (int i=x;i;i-=i&(-i)) sum+=bit[op][i]; return sum;}
int query(int op,int l,int r){
	if (op==0 || op==1) return ask(op,l);
	if (op==2) return ask(op,r)-ask(op,l-1);
	return -1;
}
int pos(int color,int cur){
	int l,r,mid,ret=dfn[cur];
	while (ret!=1 && query(2,dfn[top[cur]],dfn[cur])==(dfn[cur]-dfn[top[cur]]+1)*color){
		ret=dfn[top[cur]]; if (col[cur]==col[fa[top[cur]]]) cur=fa[top[cur]]; else return ret;
	}
	l=dfn[top[cur]]; r=dfn[cur];
	while (l<=r){mid=(l+r)>>1; if (query(2,mid,r)==(r-mid+1)*color){ret=mid; r=mid-1;} else l=mid+1;}
	return ret;
}
void change(int color,int cur,int tmp){
	while (query(2,dfn[top[cur]],dfn[cur])==(dfn[cur]-dfn[top[cur]]+1)*color){
		ins(color,dfn[top[cur]],dfn[cur],tmp);
		if (top[cur]==1) return; if (col[cur]==col[fa[top[cur]]]) cur=fa[top[cur]];
		else{ins(color,dfn[fa[top[cur]]],dfn[fa[top[cur]]],tmp); return;}
	}
	int l=dfn[top[cur]],r=dfn[cur],mid,ret=-1;
	while (l<=r){mid=(l+r)>>1; if (query(2,mid,r)==(r-mid+1)*color){ret=mid; r=mid-1;} else l=mid+1;}
	if (ret>0) ins(color,ret-1,dfn[cur],tmp); else ins(color,dfn[cur],dfn[cur],tmp);
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<n;i++){scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x);}
	
	dfs1(1); dfs2(1);
	
	for (int i=1;i<=n;i++){col[i]=1; ins(2,dfn[i],dfn[i],1); ins(1,dfn[i],dfn[i],size[i]-1);}
	
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&op,&x);
		if (op==0){xb=pos(col[x],x); printf("%d\n",query(col[x],xb,xb)+1);}
		if (op==1){
			ins(2,dfn[x],dfn[x],1-col[x]*2);
			if (x!=1){
				tmp=query(col[x],dfn[x],dfn[x]); change(col[x],fa[x],-(tmp+1));
				tmp=query(col[x]^1,dfn[x],dfn[x]); change(col[x]^1,fa[x],tmp+1);
			}
			col[x]^=1;
		}
	}
	
	return 0;
}