rt

https://www.luogu.com.cn/record/84676914

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
struct edge {
	int v, next;
} e[N << 1];
ll a[N], w[N], pos[N], sum[N], L[N], R[N], tag[N], head[N], fa[N], id[N], siz[N], top[N], depth[N], son[N];
int edge_cnt, n, q, u, v, x, cnt, awa, slen;
char opt;
int qwq(int x) {
	return tag[pos[x]] ? tag[pos[x]] : a[x];
}
int qSub(int l, int r) {
	int last = 0, ans = 0;
	for (int i = l; i <= r; i ++)
		if (qwq(i) != last) last = qwq(i), ans ++;
	return ans;
}
void rebuild(int id) {
	sum[id] = qSub(L[id], R[id]);
}
void pushdown(int id) {
	if (!tag[id]) return;
	for (int i = L[id]; i <= R[id]; i ++)
		a[i] = tag[id];
	tag[id] = 0;
}
void build() {
	slen = sqrt(n), awa = n / slen + (n % slen != 0);
	for (int id = 1; id <= awa; id ++)
		L[id] = (id - 1) * slen + 1, R[id] = id * slen;
	R[awa] = n;
	for (int id = 1; id <= awa; id ++) {
		for (int j = L[id]; j <= R[id]; j ++)
			pos[j] = id;
		rebuild(id);
	}
}
void change(int l, int r, int x) {
	int lp = pos[l], rp = pos[r];
	if (lp == rp) {
		pushdown(lp);
		for (int i = l; i <= r; i ++) a[i] = x;
		rebuild(lp);
		return;
	}
	pushdown(lp), pushdown(rp);
	for (int i = l; i <= R[lp]; i ++) a[i] = x;
	for (int id = lp + 1; id < rp; id ++) tag[id] = x, sum[id] = 1;
	for (int i = L[rp]; i <= r; i ++) a[i] = x;
	rebuild(lp), rebuild(rp);
}
ll query(int l, int r) {
	int lp = pos[l], rp = pos[r];
	ll ans = 0;
	if (lp == rp) {
		return pushdown(lp), qSub(l, r);
	}
	for (int i = lp + 1; i < rp; i ++)
		ans += sum[i] - (qwq(L[i]) == qwq(R[i - 1]));
	pushdown(lp), pushdown(rp);
	return ans + qSub(l, R[lp]) + qSub(L[rp], r) - (qwq(L[rp]) == qwq(R[rp - 1]));
}
void dfs1(int u, int f, int dep) {
	fa[u] = f, siz[u] = 1, depth[u] = dep;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (v == f) continue;
		dfs1(v, u, dep + 1);
		if (siz[v] > siz[son[u]])
			son[u] = v;
		siz[u] += siz[v];
	}
}
void dfs2(int u, int topf) {
	id[u] = ++ cnt, a[cnt] = w[u], top[u] = topf;
	if (!son[u]) return;
	dfs2(son[u], topf);
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].v;
		if (v == son[u] || v == fa[u]) continue;
		dfs2(v, v);
	}
}
int qRange(int u, int v) {
	int ans = 0, last1 = 0, last2 = 0;
	while (top[u] != top[v]) {
		if (depth[top[u]] < depth[top[v]]) swap(u, v), swap(last1, last2);
		ans += query(id[top[u]], id[u]) - (qwq(id[top[u]]) == last1);
		last1 = qwq(id[u]), u = fa[top[u]];
	}
	if (depth[u] > depth[v]) swap(u, v), swap(last1, last2);
	return ans + query(id[u], id[v]) - (qwq(id[u]) == last1) - (qwq(id[v]) == last2);
}
void updRange(int u, int v, int x) {
	while (top[u] != top[v]) {
		if (depth[top[u]] < depth[top[v]]) swap(u, v);
		change(id[top[u]], id[u], x), u = fa[top[u]];
	}
	if (depth[u] > depth[v]) swap(u, v);
	change(id[u], id[v], x);
}
void add(int u, int v) {
	e[++ edge_cnt].v = v;
	e[edge_cnt].next = head[u];
	head[u] = edge_cnt;
}
int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i ++)
		cin >> w[i];
	for (int i = 1; i < n; i ++)
		cin >> u >> v, add(u, v), add(v, u);
	dfs1(1, 0, 1), dfs2(1, 1);
	build();
	for (int i = 1; i <= q; i ++) {
		cin >> opt;
		if (opt == 'C') cin >> u >> v >> x, updRange(u, v, x);
		else cin >> u >> v, cout << qRange(u, v) << '\n';
	}
	return 0;
}