洛谷 P2486 [SDOI2011]染色

PS：如果读过题了可以跳过题目描述直接到题解部分
提交链接：洛谷 P2486 [SDOI2011]染色

题目

题目描述

给定一棵 $n$ 个节点的无根树，共有 $m$ 个操作，操作分为两种：

1. 将节点 $a$ 到节点 $b$ 的路径上的所有点（包括 $a$ 和 $b$）都染成颜色 $c$。
2. 询问节点 $a$ 到节点 $b$ 的路径上的颜色段数量。

颜色段的定义是极长的连续相同颜色被认为是一段。例如 112221 由三段组成：11、222、1。

输入格式

输入的第一行是用空格隔开的两个整数，分别代表树的节点个数 $n$ 和操作个数 $m$。

第二行有 $n$ 个用空格隔开的整数，第 $i$ 个整数 $w_i$ 代表结点 $i$ 的初始颜色。

第 $3$ 到第 $(n+1)$ 行，每行两个用空格隔开的整数 $u,v$，代表树上存在一条连结节点 $u$ 和节点 $v$ 的边。

第 $(n+2)$ 到第 $(n+m+1)$ 行，每行描述一个操作，其格式为：

每行首先有一个字符 $op$，代表本次操作的类型。

• 若 $op$ 为 C，则代表本次操作是一次染色操作，在一个空格后有三个用空格隔开的整数 $a,b,c$，代表将 $a$ 到 $b$ 的路径上所有点都染成颜色 $c$。
• 若 $op$ 为 Q，则代表本次操作是一次查询操作，在一个空格后有两个用空格隔开的整数 $a,b$，表示查询 $a$ 到 $b$ 路径上的颜色段数量。

输出格式

对于每次查询操作，输出一行一个整数代表答案。

样例 #1

样例输入 #1

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5
1
2
3
4
5
6
7
8
9
10
11
12

样例输出 #1

3
1
2
1
2
3

提示

数据规模与约定

对于 $100\%$ 的数据，$1\le n,m\le 10^5$，$1\le w_i,c\le 10^9$，$1\le a,b,u,v\le n$，$op$ 一定为 C 或 Q，保证给出的图是一棵树。

除原数据外，还存在一组不计分的 hack 数据。

题解

这道题我们看到是要维护树上路径，就可以想到LCA和树链剖分（因为我写的树链剖分，所以后面就以树链剖分为例），用线段树维护区间左端点的颜色、区间右端点的颜色和区间内颜色段的数量三个区间信息。

在维护区间内颜色段的数量的时候要记得，如果左儿子的右端点和右儿子的左端点颜色相同，段数要减一。查询的时候也要注意这一点。

至于其他的，就和树链剖分的基本操作一样了。

代码实现

100pts

//洛谷 P2486 [SDOI2011]染色
#pragma GCC optimize(3)
#include
#include
#include
#define maxn 400010
using namespace std;
int n,m;
int col[maxn];
int nc;
int head[maxn];
int cnt;
int u,v;
int siz[maxn];
int dep[maxn];
int son[maxn];
int fa[maxn];
int dfn[maxn];
int rnk[maxn];
int top[maxn];
int op,c;

struct edge{
	int v,nex;
}a[maxn<<1];

struct tree{
	int l,r,d,tag;
	tree(){
		tag=0;
	}
}b[maxn<<2];

void in(int &x){
	int nt;
	x=0;
	while(!isdigit(nt=getchar()));
	x=nt^'0';
	while(isdigit(nt=getchar())){
		x=(x<<3)+(x<<1)+(nt^'0');
	}
}

void build(int u,int v){
	a[++cnt].v=v;
	a[cnt].nex=head[u];
	head[u]=cnt;
}

void dfs1(int x){
	siz[x]=1;
	for(int i=head[x];i;i=a[i].nex){
		int v=a[i].v;
		if(v!=fa[x]){
			fa[v]=x;
			dep[v]=dep[x]+1;
			dfs1(v);
			siz[x]+=siz[v];
			if(siz[v]>siz[son[x]]){
				son[x]=v;
			}
		}
	}
}

void dfs2(int x,int tp){
	top[x]=tp;
	dfn[x]=++cnt;
	rnk[cnt]=x;
	if(son[x]){
		dfs2(son[x],tp);
	}
	else{
		return;
	}
	for(int i=head[x];i;i=a[i].nex){
		int v=a[i].v;
		if(v!=son[x]&&v!=fa[x]){
			dfs2(v,v);
		}
	}
}

void build1(int rt,int l,int r){
	if(l==r){
		b[rt].l=b[rt].r=col[rnk[l]];
		b[rt].d=1;
		return;
	}
	int mid=(l+r)>>1;
	build1(rt<<1,l,mid);
	build1(rt<<1|1,mid+1,r);
	b[rt].l=b[rt<<1].l;
	b[rt].r=b[rt<<1|1].r;
	b[rt].d=b[rt<<1].d+b[rt<<1|1].d;
	if(b[rt<<1].r==b[rt<<1|1].l){
		--b[rt].d;
	}
}

void push(int rt,int l,int r,int mid){
	b[rt<<1].tag=b[rt<<1|1].tag=b[rt<<1].l=b[rt<<1|1].l=b[rt<<1].r=b[rt<<1|1].r=b[rt].tag;
	b[rt<<1].d=b[rt<<1|1].d=1;
	b[rt].tag=0;
}

void ch(int rt,int l,int r,int ll,int rr,int c){
	if(l>=ll&&r<=rr){
		b[rt].l=b[rt].r=c;
		b[rt].d=1;
		b[rt].tag=c;
		return;
	}
	int mid=(l+r)>>1;
	if(b[rt].tag){
		push(rt,l,r,mid);
	}
	if(ll<=mid){
		ch(rt<<1,l,mid,ll,rr,c);
	}
	if(rr>mid){
		ch(rt<<1|1,mid+1,r,ll,rr,c);
	}
	b[rt].l=b[rt<<1].l;
	b[rt].r=b[rt<<1|1].r;
	b[rt].d=b[rt<<1].d+b[rt<<1|1].d;
	if(b[rt<<1].r==b[rt<<1|1].l){
		--b[rt].d;
	}
}

void change(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){
			swap(x,y);
		}
		ch(1,1,n,dfn[top[x]],dfn[x],k);
		x=fa[top[x]];
	}
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	ch(1,1,n,dfn[y],dfn[x],k);
}

int qu(int rt,int l,int r,int ll,int rr){
	if(l>=ll&&r<=rr){
		return b[rt].d;
	}
	int mid=(l+r)>>1;
	if(b[rt].tag){
		push(rt,l,r,mid);
	}
	int ans=0;
	if(ll<=mid){
		ans+=qu(rt<<1,l,mid,ll,rr);
	}
	if(rr>mid){
		ans+=qu(rt<<1|1,mid+1,r,ll,rr);
	}
	if(ll<=mid&&rr>mid&&b[rt<<1].r==b[rt<<1|1].l){
		--ans;
	}
	return ans;
}

int qc(int rt,int l,int r,int x){
	if(l==x){
		return b[rt].l;
	}
	if(r==x){
		return b[rt].r;
	}
	int mid=(l+r)>>1;
	if(b[rt].tag){
		push(rt,l,r,mid);
	}
	if(x<=mid){
		return qc(rt<<1,l,mid,x);
	}
	else{
		return qc(rt<<1|1,mid+1,r,x);
	}
}

int query(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){
			swap(x,y);
		}
		ans+=qu(1,1,n,dfn[top[x]],dfn[x]);
		x=top[x];
		if(qc(1,1,n,dfn[fa[x]])==qc(1,1,n,dfn[x])){
			--ans;
		}
		x=fa[x];
	}
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	ans+=qu(1,1,n,dfn[y],dfn[x]);
	return ans;
}

int main(){
	register int i;
	in(n),in(m);
	for(i=1;i<=n;++i){
		in(col[i]);
	}
	for(i=1;i<n;++i){
		in(u),in(v);
		build(u,v);
		build(v,u);
	}
	dep[1]=1;
	dfs1(1);
	cnt=0;
	dfs2(1,1);
	build1(1,1,n);
	for(i=1;i<=m;++i){
		char op[2];
		scanf("%s",op);
		in(u),in(v);
		if(op[0]=='C'){
			in(c);
			change(u,v,c);
		}
		else{
			printf("%d\n",query(u,v));
		}
	}
	return 0;
}
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235