染色

题意

给定一棵有n个节点的无根树和m个操作,操作有2类:

1、将节点a到节点b路径上所有点都染成颜色c;

2、询问节点a到节点b路径上的颜色段数量(连续相同颜色被认为是同一段),

如“112221”由3段组成:“11”、“222”和“1”。

请你写一个程序依次完成这m个操作。

分析

轻重链剖分后线段树区间合并

注意

  1. 线段树查询的时候,递归查询左右两个子段时,如果交界处颜色相等,答案要减一
  2. 在树链上查询的时候,如果链首的父亲和链首颜色相同,答案要减一

代码

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
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e5 + 5;
int a[maxn];
struct Node {
int l, r, cnt;
};
struct HLD {
int n, dfn;
int sz[maxn], top[maxn], son[maxn], dep[maxn], par[maxn], id[maxn],
rk[maxn];
Node seg[maxn << 2];
int lazy[maxn << 2];
vector<int> G[maxn];
void init(int n) {
this->n = n;
clr(son, -1);
dfn = 0;
for (int i = 0; i <= n; i++) G[i].clear();
}
void addedge(int u, int v) {
G[u].pb(v);
G[v].pb(u);
}
void dfs(int u, int fa, int d) {
dep[u] = d;
par[u] = fa;
sz[u] = 1;
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v == fa) continue;
dfs(v, u, d + 1);
sz[u] += sz[v];
if (son[u] == -1 || sz[v] > sz[son[u]]) son[u] = v;
}
}
void link(int u, int t) {
top[u] = t;
id[u] = ++dfn;
rk[dfn] = u;
if (son[u] == -1) return;
link(son[u], t);
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (v != son[u] && v != par[u]) link(v, v);
}
}
void pushup(int rt) {
seg[rt].cnt = seg[lson].cnt + seg[rson].cnt;
seg[rt].l = seg[lson].l;
seg[rt].r = seg[rson].r;
if (seg[lson].r == seg[rson].l) seg[rt].cnt--;
}
void build(int l, int r, int rt) {
lazy[rt] = -1;
if (l == r) {
seg[rt].l = seg[rt].r = a[rk[l]];
seg[rt].cnt = 1;
return;
}
int m = l + r >> 1;
build(l, m, lson);
build(m + 1, r, rson);
pushup(rt);
}
void pushdown(int rt) {
if (lazy[rt] == -1) return;
int c = lazy[rt];
seg[lson].l = seg[rson].l = c;
seg[lson].r = seg[rson].r = c;
seg[lson].cnt = seg[rson].cnt = 1;
lazy[lson] = lazy[rson] = c;
lazy[rt] = -1;
}
void update(int l, int r, int L, int R, int rt, int c) {
if (L <= l && R >= r) {
seg[rt].l = seg[rt].r = c;
seg[rt].cnt = 1;
lazy[rt] = c;
return;
}
pushdown(rt);
int m = l + r >> 1;
if (L <= m) update(l, m, L, R, lson, c);
if (R > m) update(m + 1, r, L, R, rson, c);
pushup(rt);
}
void update_path(int u, int v, int c) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
update(1, n, id[top[u]], id[u], 1, c);
u = par[top[u]];
}
// if (u == v) return;
if (dep[u] > dep[v]) swap(u, v);
update(1, n, id[u], id[v], 1, c);
}
int query_c(int l, int r, int x, int rt) {
if (l == r) return seg[rt].l;
pushdown(rt);
int m = l + r >> 1;
if (x <= m) return query_c(l, m, x, lson);
if (x > m) return query_c(m + 1, r, x, rson);
}
int query(int l, int r, int L, int R, int rt) {
if (L <= l && R >= r) {
return seg[rt].cnt;
}
pushdown(rt);
int m = l + r >> 1;
int ret = 0;
if (R <= m) {
ret += query(l, m, L, R, lson);
} else if (L > m) {
ret += query(m + 1, r, L, R, rson);
} else {
ret += query(m + 1, r, L, R, rson) + query(l, m, L, R, lson);
if(seg[lson].r == seg[rson].l) ret--;
}
// if (L <= m) ret += query(l, m, L, R, lson);
// if (R > m) ret += query(m + 1, r, L, R, rson);
return ret;
}
int query_path(int u, int v) {
int ret = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret += query(1, n, id[top[u]], id[u], 1);
int fac = query_c(1, n, id[par[top[u]]], 1);
int c = query_c(1, n, id[top[u]], 1);
if (fac == c) ret--;
u = par[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ret += query(1, n, id[u], id[v], 1);
return ret;
}
};
HLD hld;

int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
int n, m;
while (cin >> n >> m) {
int u, v, c;
hld.init(n);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 0; i < n - 1; i++) {
cin >> u >> v;
hld.addedge(u, v);
}
hld.dfs(1, 1, 1);
hld.link(1, 1);
hld.build(1, n, 1);
string op;
for (int i = 0; i < m; i++) {
cin >> op;
if (op == "C") {
cin >> u >> v >> c;
hld.update_path(u, v, c);
} else {
cin >> u >> v;
cout << hld.query_path(u, v) << endl;
}
}
}
}
Thank you for your support!