洛谷P2486 [SDOI2011]染色（树链剖分初入门）

首先,根据本人以往解决经验这类疑似树上区间操作,都可能是树链剖分,我们先考虑数组的实现情况
给你一个数组$ai$,有2个操作
$操作1:[l,r,color]:[l,r]变成color色$
$操作2:查询[l,r]颜色段的数目$
这是线段树染色的一个东西,解决方法如下:
线段树维护3个值$区间颜色数量num,左端点颜色cl,右端点颜色cr$
考虑区间之间的合并:
如果左区间$L$的$cr$与右区间$R$的$cl$一样,说明有一段染色横跨了两个区间.那么总的染色数目会减少1.$num[fa]=num[L]+num[R]-1$
否则,两个区间之间没有交叉,颜色数目都是独立的.$num[fa]=num[L]+num[R]$
解决完核心的区间合并问题,我们就可以尝试书写线段树部分并套用树链剖分即可.
很快我们发现仍然有问题,因为线段树部分只能在重链部分是有效的,我们需要人为去合并重链之间的信息.
当让$depth[x]$较大的点往上跳的时候,记录前一次跳的时候较浅的点的颜色(就是线段树查询里边的左端点的颜色,因为深度小的结点在线段树映射的id也小),如果查询到的链条的右端点与上一次的左端点颜色相同,那么它们本来是同一段颜色,应当减一.

基于这个想法:我们用$cl$记录上一次$x$跳完后左端点区间的颜色,也就是$top[x]$的颜色,用$cr$记录$cl$上一次更替的值.
首先,$cl$是为了帮助我们解决上边的问题的,也就是$x$往上跳到新的重链的时候,$之前的top[x]$与新链最下边的颜色是否相同,如果相同那么则要减少1,因为他们属于同一个颜色块.
有代码$if(cl==t.cr)ans--$,$t.cr$是本次跳到新链后最下边的那个点.
然而,因为这个$x$跳到$Lca(x,y)$的过程是两个点反复横跳的过程,所以我们还需要一个$cr$来记录另外一边(也就是y那边)对应的那个$cl$.
当我们执行了$if(depth[top[x]]<depth[top[y]])swap(x,y)$,点$x,y$发生了变化,那么它们的$cl,cr$也要交换一边,
要保证当前跳的这个点的$x$,它底下那个点是$cl$.用图像来表示,就会看到以下图片.

特别的,如果某个点到了$lca(x,y)$,也就是处以同一块重链的时候,我们会完成最后的跳跃.但请特别注意,此时$x,y$这两个点已经被之前的两个段计算过了,所以如果$x,y$这两个点如果和$cl,cr$有重复的颜色,那么答案要相应减少
也就是
这里的$tr.cl$就是$x$,$tr.cr$就是$y$.在最后我们保证了$depth[x]$是较大的.
$if(cl==tr.cl)ans--$ $if(cr==tr.cr)ans--$
148行痛苦ac代码:
第一次尝试写详细的树链剖分题解,还不是很熟练

/*
You held me down but I broke free,
I found the love inside of me.
Now I don't need a hero to survive
Cause I already saved my life.
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
int a[maxn];int tag[maxn*4+5];
//线段树部分
#define L (idx<<1)
#define R (idx<<1|1)
#define MID (start+end>>1)
struct Node{
	int num,cl,cr;
}tree[maxn*4+5];
void push_up(int idx){
	if(tree[L].cr==tree[R].cl) tree[idx].num = tree[L].num + tree[R].num -1;
	else tree[idx].num = tree[L].num + tree[R].num;
	//maintain cl,cr;
	tree[idx].cl = tree[L].cl;tree[idx].cr = tree[R].cr;
}
void build(int idx,int start,int end){
	if(start==end) {
		tree[idx].cl = tree[idx].cr = a[start];
        tree[idx].num = 1;
		return ;
	}
	build(L,start,MID);build(R,MID+1,end);
	push_up(idx);
}
void push_down(int idx,int start,int end){
	if(tag[idx]==0) return ;
	//pushdown的子节点全部被染色成tag[idx],颜色段也改成1
	tree[L].cl = tree[L].cr = tree[R].cl = tree[R].cr = tag[idx];
	tree[L].num = tree[R].num =1;
	tag[L] = tag[R] = tag[idx];
	tag[idx]=0;
}
void update(int idx,int start,int end,int l,int r,int k){
	if(start>=l&&end<=r){
		tree[idx].cl = tree[idx].cr = k;tree[idx].num =1;
		tag[idx] = k;
		return ;
	}
	push_down(idx,start,end);
	if(l<=MID) update(L,start,MID,l,r,k);
	if(r>MID) update(R,MID+1,end,l,r,k);
	push_up(idx);
}
Node query(int idx,int start,int end,int l,int r){
	if(start>=l&&end<=r) return tree[idx];
	push_down(idx,start,end);
	if(l<=MID&&r>MID){
		Node t1 = query(L,start,MID,l,r);Node t2 = query(R,MID+1,end,l,r);
		if(t1.cr==t2.cl) return (Node){t1.num+t2.num-1,t1.cl,t2.cr};
		return (Node){t1.num+t2.num,t1.cl,t2.cr};
	}
	else if(l<=MID) return query(L,start,MID,l,r);
	return query(R,MID+1,end,l,r);
}
//接下来是树链剖分的内容
int son[maxn],fa[maxn],depth[maxn],top[maxn],siz[maxn];int dfs_clock=0;//dfs序
vector<int> G[maxn];int n;//图的大小,树一共有多少节点
//u的重儿子,父亲,深度,顶端重儿子编号,u为子树的节点大小.
int val[maxn],id[maxn];//剖分后,每个点得到一个新的连续编号,在同一链上,id为连续的,故可线段树处理
void dfs1(int u,int f){
	depth[u]=depth[f]+1;fa[u]=f;siz[u]=1;
	for(auto v : G[u]){
		if(v==f) continue;
		dfs1(v,u);siz[u]+=siz[v];
		if(son[u]==0||siz[son[u]]<siz[v]) son[u]=v;
	}
}
void dfs2(int u,int topf){
	id[u]=++dfs_clock;a[id[u]]=val[u];//把原点权赋值到线段树上
	top[u]=topf;
	if(son[u]) dfs2(son[u],topf);
	for(auto v : G[u]){
		if(v==fa[u]||v==son[u]) continue;
		dfs2(v,v);
	}
}
//树链剖分与线段树连接部分
//1.查询树上x,y路径上点权和 在一条链上,top[x]实际上是该链编号的起点
//因为dfs序一定先访问到了top[x],再访问到x,查询范围就是[id[top[x],id[x]]
int tr_query(int x,int y){
	int cl = 0,cr = 0;
	int ans = 0;
	while(top[x]!=top[y]){
		//当x,y不再同一个链上,需要先类似倍增思想跳到同一个链上
		//默认x为较深的点
		if(depth[top[x]]<depth[top[y]]) swap(x,y),swap(cl,cr);
		Node t = query(1,1,n,id[top[x]],id[x]);
		ans += t.num;
		if(t.cr==cl) ans--;
		cl = t.cl;
		x = fa[top[x]];//跳到一条新的链上
	}
	if(depth[x]>depth[y]) swap(x,y),swap(cl,cr);
	//默认x的depth较小,则id[x]即为较小的那个,此时已经在同一链上
	Node t = query(1,1,n,id[x],id[y]);ans+=t.num;
	if(cl==t.cl) ans--;
	if(cr==t.cr) ans--;
	return ans;
}
//2.对于树上两个节点x,y, 其路径上全部加上权值val
//同1操作即可
void tr_update(int x,int y,int k){
	while(top[x]!=top[y]){
		if(depth[top[x]]<depth[top[y]]) swap(x,y);
		update(1,1,n,id[top[x]],id[x],k);
		x = fa[top[x]];
	}
	if(depth[x]>depth[y]) swap(x,y);
	update(1,1,n,id[x],id[y],k);
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m;cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>val[i];
	for(int i=1;i<=n-1;i++){
		int u,v;cin>>u>>v;
		G[u].pb(v);G[v].pb(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	while(m--){
		char op;cin>>op;
		if(op=='C'){
			int a,b,c;cin>>a>>b>>c;
			tr_update(a,b,c);
		}
		else{
			int a,b;cin>>a>>b;
			cout<<tr_query(a,b)<<"\n";
		}
	}
}
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