Problems Website
- SDOI_2011染色
Solution
- 又是一道熟练剖分的好题，区别是这一次的线段树要维护的信息有所不同，要维护4个东西：$num$(区间内不同颜色的数量)、$lc$(区间最左端的颜色)、$rc$(区间最右端的颜色)、$tag$(染色标记)，在$pushup$时要注意，如果左儿子的$rc$等于右儿子的$lc$，则父亲的$num$等于他们的$num$之和$-1$，因为有重合的颜色。
- 还有一点，在执行$Q$操作时也要判重，我们设$lc$为当前链的左端点的颜色，$rc$为当前链右端点的颜色，$pos1$为当前要往上跳的路径\上次的终点颜色，$pos2$为另一条路径\上一次的终点颜色，在往跳同一条链时，如果$pos1==rc$，则计量数$—$,在同一条链时，如果$lc==pos1$、$rc==pos2$,同样要减计量数。
- 原因：当出现上述情况时，明显是颜色重合，所以要减。
Code
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
typedef long long ll;
const int Maxn = 1e5 + 10;
inline ll sc() {
ll xx = 0, ff = 1; char cch = gc;
while(!isdigit(cch)) {
if(cch == '-') ff = -1; cch = gc;
}
while(isdigit(cch)) {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
inline ll out(ll x) {
if(x < 0) pc('-'), x = -x;
if(x >= 10)
out(x / 10);
pc(x % 10 + '0');
}
struct node {
ll next, to;
}t[Maxn << 1];
struct LST {
ll num, tags, lc, rc;
}lst[Maxn << 2];
ll n, m, cnt, pos1, pos2, lc, rc;
ll a[Maxn], head[Maxn], dep[Maxn], son[Maxn], fa[Maxn], siz[Maxn], top[Maxn], rid[Maxn], id[Maxn];
inline void ADD(ll from, ll to) {
t[++cnt].next = head[from];
t[cnt].to = to;
head[from] = cnt;
}
inline void dfs1(ll now, ll Fa) {
dep[now] = dep[Fa] + 1;
fa[now] = Fa;
siz[now] = 1;
for(re int i = head[now]; i; i = t[i].next) {
ll to = t[i].to;
if(to == Fa) continue;
dfs1(to, now);
siz[now] += siz[to];
if(siz[son[now]] < siz[to])
son[now] = to;
}
}
inline void dfs2(ll now, ll topf) {
top[now] = topf;
id[now] = ++cnt;
rid[cnt] = now;
if(!son[now]) return;
dfs2(son[now], topf);
for(re int i = head[now]; i; i = t[i].next) {
ll to = t[i].to;
if(to == son[now] || to == fa[now]) continue;
dfs2(to, to);
}
}
inline void pushup(ll k) {
lst[k].num = lst[k << 1].num + lst[k << 1 | 1].num;
if(lst[k << 1].rc == lst[k << 1 | 1].lc) --lst[k].num;
lst[k].lc = lst[k << 1].lc;
lst[k].rc = lst[k << 1 | 1].rc;
}
inline void build(ll k, ll l, ll r) {
if(l == r) {
lst[k].lc = lst[k].rc = a[rid[l]];
lst[k].num = 1;
return;
}
ll mid = l + r >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
pushup(k);
}
inline void pushdown(ll k, ll l, ll r) {
if(!lst[k].tags) return;
lst[k << 1].lc = lst[k << 1 | 1].lc = lst[k << 1].rc = lst[k << 1 | 1].rc = lst[k << 1].tags = lst[k << 1 | 1].tags = lst[k].tags;
lst[k << 1].num = lst[k << 1 | 1].num = 1;
lst[k].tags = 0;
}
inline void modify(ll k, ll l, ll r, ll x, ll y, ll z) {
if(x <= l && r <= y) {
lst[k].lc = lst[k].rc = lst[k].tags = z;
lst[k].num = 1;
return ;
}
pushdown(k, l, r);
ll mid = l + r >> 1;
if(x <= mid) modify(k << 1, l, mid, x, y, z);
if(y > mid) modify(k << 1 | 1, mid + 1, r, x, y, z);
pushup(k);
}
inline ll query(ll k, ll l, ll r, ll x, ll y) {
if(x <= l && r <= y) {
if(x == l) lc = lst[k].lc;
if(r == y) rc = lst[k].rc;
return lst[k].num;
}
pushdown(k, l, r);
ll mid = l + r >> 1;
if(y <= mid) return query(k << 1, l, mid, x, y);
if(x > mid) return query(k << 1 | 1, mid + 1, r, x, y);
ll res = query(k << 1, l, mid, x, y) + query(k << 1 | 1, mid + 1, r, x, y);
if(lst[k << 1].rc == lst[k << 1 | 1].lc) --res;
return res;
}
inline void uptree(ll x, ll y, ll z) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) std :: swap(x, y);
modify(1, 1, n, id[top[x]], id[x], z);
x = fa[top[x]];
}
if(id[x] > id[y]) std :: swap(x, y);
modify(1, 1, n, id[x], id[y], z);
}
inline ll qy(ll x, ll y) {
ll res = 0;
pos1 = pos2 = 0;
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) std :: swap(x, y), std :: swap(pos1, pos2);
res += query(1, 1, n, id[top[x]], id[x]);
if(rc == pos1) --res;
pos1 = lc, x = fa[top[x]];
}
if(id[x] > id[y]) std :: swap(x, y), std :: swap(pos1, pos2);
res += query(1, 1, n, id[x], id[y]);
if(lc == pos1) --res;
if(rc == pos2) --res;
return res;
}
int main() {
n = sc(), m = sc();
for(re int i = 1; i <= n; ++i)
a[i] = sc();
for(re int i = 1; i < n; ++i) {
int x = sc(), y = sc();
ADD(x, y), ADD(y, x);
}
cnt = 0;
dfs1(1, 0), dfs2(1, 1), build(1, 1, n);
while(m--) {
char c[2];
std :: cin >> c[0];
int x = sc(), y = sc();
if(c[0] == 'Q') {
out(qy(x, y)), pc('\n');
}
else {
int z = sc();
uptree(x, y, z);
}
}
return 0;
}
// Coded by dy.
rp++