题面：[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

1
2
3
4
5
6
7
8
9
10
11
12
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

1
2
3
3
1
2

提示

数据规模与约定

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

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

思路

首先，这个是树剖还是显然的。但是这时候要处理颜色段数量，那就要从线段树的维护方式入手了。我们发现，两个线段合并的时候，如果前面的尾和后面的首一样，那么结果就是两边段数的和减去一，否则就是直接段数相加。那么不难想到线段树顺便记录一个当前线段的左右就可以了。

然后题目还提到了一个区间染色的操作，这就发现了一个重要的内容，我们一定是还需要记录一个懒惰标记的，但是懒惰标记显而易见也不是原来的意思了，我们打上懒惰标记表示这一段都是这个颜色即可。

查询过程有点特殊，由于树剖存在左右跳的情况，这时候要让前后两段的两端接上，就需要分别存下两端的最后一次的顶端颜色，大体按照对于树剖的理解就可以直接写过，是一道水紫。

然后还有些细节问题，普通线段树的建树是需要用 cntd 对应 节点u 的。

代码

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

const int N = 1e5 + 10;

int n, Q;
int a[N];
Graph< N, N << 1 >G;

inline void Input() {
    read(n, Q);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
    int u, v;
    for(int i = 1; i < n; i++) {
        read(u, v);
        G.AddEdge(u, v);
        G.AddEdge(v, u);
    }
}

int fa[N], dep[N];
int sz[N], son[N];
int top[N];
int id[N], rk[N], cntd;

void Dfs(int u, int F) {
    fa[u] = F, dep[u] = dep[F] + 1, sz[u] = 1;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == F) continue;
        Dfs(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}

void Dfs2(int u, int t) {
    top[u] = t;
    id[u] = ++cntd;
    rk[cntd] = u;
    if(!son[u]) return ;
    Dfs2(son[u], t);
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == fa[u] || v == son[u]) continue;
        Dfs2(v, v);
    }
}

struct Node {
    int lc, rc, cnt, lazy;
    int L, R;
}node[N << 4];

inline void PushUp(int p) {
    node[p].lc = node[p << 1].lc;
    node[p].rc = node[p << 1 | 1].rc;
    node[p].cnt = node[p << 1].cnt + node[p << 1 | 1].cnt;
    if(node[p << 1].rc == node[p << 1 | 1].lc) node[p].cnt--;
}
inline void Add(int p, int val) {
    node[p].lc = node[p].rc = val;
    node[p].cnt = 1, node[p].lazy = val;
}
inline void PushDown(int p) {
    if(!node[p].lazy) return ;
    Add(p << 1, node[p].lazy);
    Add(p << 1 | 1, node[p].lazy);
    node[p].lazy = 0;
}

void Build(int p, int L, int R) {
    node[p].L = L, node[p].R = R, node[p].lazy = 0;
    if(L == R) {
        node[p].cnt = 1;
        node[p].lc = node[p].rc = a[rk[L]];
        return ;
    }
    int mid = L + R >> 1;
    Build(p << 1, L, mid);
    Build(p << 1 | 1, mid + 1, R);
    PushUp(p);
}

void Modify(int p, int L, int R, int val) {
    if(L <= node[p].L && node[p].R <= R) {
        Add(p, val);
        return ;
    }
    PushDown(p);
    int mid = node[p].L + node[p].R >> 1;
    if(L <= mid) Modify(p << 1, L, R, val);
    if(mid < R) Modify(p << 1 | 1, L, R, val);
    PushUp(p);
}

int LC, RC;
int Query(int p, int L, int R) {
    // cout << p << endl;
    if(L <= node[p].L && node[p].R <= R) {
        if(node[p].L == L) LC = node[p].lc;
        if(node[p].R == R) RC = node[p].rc;
        return node[p].cnt;
    }
    PushDown(p);
    int mid = node[p].L + node[p].R >> 1;
    if(R <= mid) return Query(p << 1, L, R);
    else if(mid < L) return Query(p << 1 | 1, L, R);
    else {
        int ans = Query(p << 1, L, R) + Query(p << 1 | 1, L, R);
        if(node[p << 1].rc == node[p << 1 | 1].lc) ans--;
        return ans;
    }
}

inline void ChangeC(int u, int v, int c) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        Modify(1, id[top[u]], id[u], c);
        u = fa[top[u]];
    }
    if(id[u] > id[v]) swap(u, v);
    Modify(1, id[u], id[v], c);
}

inline void QuerySG(int u, int v) {
    int ans = 0, l = 0, r = 0;
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]]) swap(u, v), swap(l, r);
        ans += Query(1, id[top[u]], id[u]);
        if(RC == l) ans--;
        l = LC;
        u = fa[top[u]];
    }
    if(id[u] > id[v]) swap(u, v), swap(l, r);
    ans += Query(1, id[u], id[v]);
    ans -= (LC == l) + (RC == r);
    printf("%d\n", ans);
}

inline void Work() {
    Dfs(1, 1), Dfs2(1, 1);
    Build(1, 1, n);
    char op[10]; int u, v, c;
    while(Q--) {
        scanf("%s%d%d", op, &u, &v);
        if(op[0] == 'C') {
            read(c);
            ChangeC(u, v, c);
        }
        else {
            QuerySG(u, v);
        }
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}