luogu2486[SDOI2011]染色题解--树链剖分+Trick

题目链接

https://www.luogu.org/problemnew/show/P2486

分析

看上去又是一道强行把序列上问题搬运到树上的裸题,然而分析之后发现并不然…

首先我们考虑如何在序列上维护信息:从最简单的想起,如果两个相邻的元素合并,显然是这两个元素所含颜色段个数(其实就是1)加起来,如果两个元素颜色相同就减1;那么两个分别含有两个元素的相邻区间合并,还是把这两个区间所含颜色段个数加起来,如果左区间最右边的颜色等于右区间最左边的颜色就减去1.

如此我们已经得到线段树维护信息的方法,记录区间所含颜色段个数,区间最左边颜色及区间最右边颜色,当然为了$pushdown$我们还得维护一个$tag$数组表示覆盖标记,然后按上面方法就好了

但是在树链剖分查询两点之间时就与序列上不同了.有一个问题,就是当前链最左边的颜色如果和上面那条链最右边的颜色相等的话,需要将贡献减1.有一个$naiive$的方法是每次查询链时再查一下上面那条链最右边的颜色(其实就是单点查询$fa[top[x]]$的颜色),然后这个方法看起来不优美,其实有个更妙的方法

我们每次查完一条链后记录该链最左边的颜色,同时将该链最右边的颜色与上一次记录的值比较。看起来很容易但有个问题就是你可能是从$LCA$两个不同的子树上向LCA跳,然后从 @ qscqesze_lca 的题解中学到了一个小trick轻易解决了这个问题,请看代码

代码

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cstdlib>
#include <vector>
#define ll long long 
#define ri register int 
#define ull unsigned long long 
using std::min;
using std::max;
using std::swap;
template <class T>inline void read(T &x){
	x=0;int ne=0;char c;
	while(!isdigit(c=getchar()))ne=c=='-';
	x=c-48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
	x=ne?-x:x;return ;
}
const int maxn=100005;
const int inf=0x7fffffff;
int n,m;
struct Edge{
	int ne,to;
}edge[maxn<<1];
int h[maxn],num_edge=1;
inline void add_edge(int f,int to){
	edge[++num_edge].ne=h[f];
	edge[num_edge].to=to;
	h[f]=num_edge;
}
int col[maxn];
int dep[maxn],fa[maxn],size[maxn],dfn[maxn],rnk[maxn],tot=0,top[maxn],son[maxn];
void dfs_1(int now){
	int v;size[now]=1;
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now])continue;
		dep[v]=dep[now]+1,fa[v]=now;
		dfs_1(v);
		size[now]+=size[v];
		if(!son[now]||size[v]>size[son[now]])son[now]=v;
	}
	return ;
}
void dfs_2(int now,int t){
	int v;top[now]=t,dfn[now]=++tot,rnk[tot]=now;
	if(!son[now])return ;
	dfs_2(son[now],t);
	for(ri i=h[now];i;i=edge[i].ne){
		v=edge[i].to;
		if(v==fa[now]||v==son[now])continue;
		dfs_2(v,v);
	}
	return ;
}
int num[maxn<<2],lc[maxn<<2],rc[maxn<<2],tag[maxn<<2];
int L,R,dta;
void build(int now,int l,int r){
	tag[now]=-1;
	if(l==r){
		num[now]=1;
		lc[now]=rc[now]=col[rnk[l]];
		return ;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	num[now]=num[now<<1]+num[now<<1|1]-(rc[now<<1]==lc[now<<1|1]?1:0);
	lc[now]=lc[now<<1],rc[now]=rc[now<<1|1];
	return ;
}
inline void pushdown(int now){
	if(tag[now]!=-1){
		tag[now<<1]=tag[now<<1|1]=tag[now];
		lc[now<<1]=lc[now<<1|1]=lc[now];
		rc[now<<1]=rc[now<<1|1]=rc[now];
		num[now<<1]=num[now<<1|1]=1;
		tag[now]=-1;
	}
	return ;
}
void update(int now,int l,int r){
	if(L<=l&&r<=R){
		num[now]=1;
		lc[now]=rc[now]=dta;
		tag[now]=dta;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(now);
	if(L<=mid)update(now<<1,l,mid);
	if(mid<R)update(now<<1|1,mid+1,r);
	num[now]=num[now<<1]+num[now<<1|1]-(rc[now<<1]==lc[now<<1|1]?1:0);
	lc[now]=lc[now<<1],rc[now]=rc[now<<1|1];
	return ;
}
int chain_lc,chain_rc;
int query(int now,int l,int r){
	if(L==l)chain_lc=lc[now];
	if(R==r)chain_rc=rc[now];
	if(L<=l&&r<=R){
		return num[now];
	}
	int ans=0,mid=(l+r)>>1;
	pushdown(now);
	if(L<=mid&&mid<R)ans=query(now<<1,l,mid)+query(now<<1|1,mid+1,r)-(rc[now<<1]==lc[now<<1|1]?1:0);
	else if(L<=mid)ans=query(now<<1,l,mid);
	else if(mid<R)ans=query(now<<1|1,mid+1,r);
    //num[now]=num[now<<1]+num[now<<1|1]-(rc[now<<1]==lc[now<<1|1]?1:0);
	//lc[now]=lc[now<<1],rc[now]=rc[now<<1|1];
	return ans;
}
inline void update_path(int x,int y,int c){
	dta=c;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		L=dfn[top[x]],R=dfn[x];
		update(1,1,n);
		x=fa[top[x]];
	}
	if(dfn[x]>dfn[y])swap(x,y);
	L=dfn[x],R=dfn[y];
	update(1,1,n);
	return ;
}
int lst_1,lst_2;//lst_1总是你当前正在查询的链的上一条链的最左边颜色 
inline void query_path(int x,int y){
	int ans=0;
	lst_1=lst_2=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
		   {swap(x,y),swap(lst_1,lst_2);}//非常高明的一个trick,不用刻意查询链top父亲的颜色 
		L=dfn[top[x]],R=dfn[x];	
		ans+=query(1,1,n);
		if(lst_1==chain_rc)ans--;
		lst_1=chain_lc;
		x=fa[top[x]];
	}
	if(dfn[x]<dfn[y])
		{swap(x,y),swap(lst_1,lst_2);}
	L=dfn[y],R=dfn[x];
	ans+=query(1,1,n);
	if(chain_rc==lst_1)ans--;
	if(chain_lc==lst_2)ans--;
	printf("%d\n",ans);
	return ;
}
int main(){
	int x,y,z;
	read(n),read(m);
	for(ri i=1;i<=n;i++)read(col[i]);
	for(ri i=1;i<n;i++){
		read(x),read(y);
		add_edge(x,y);
		add_edge(y,x);
	}
	dep[1]=1,fa[1]=0;
	dfs_1(1);
	dfs_2(1,1);
	build(1,1,n);
	char opt[5];
	while(m--){
		scanf("%s",opt);
		if(opt[0]=='C'){
			read(x),read(y),read(z);
			update_path(x,y,z);
		}
		else{
			read(x),read(y);
			query_path(x,y);
		}
	}
	return 0;
}