树链剖分裸题。
线段树统计“答案”、“前缀字符”、“后缀字符”三个信息就可以很方便的合并了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100000 + 5;
int n, m;
int head[maxn], nxt[maxn * 4], to[maxn * 4], cnt;
void inline addEdge(int u, int v) {
nxt[++cnt] = head[u], to[cnt] = v, head[u] = cnt;
nxt[++cnt] = head[v], to[cnt] = u, head[v] = cnt;
}
namespace Tree
{
// PartI. Tree
int col[maxn], son[maxn], fa[maxn], top[maxn], size[maxn], deep[maxn], dfn[maxn], org[maxn], dfs_clock;
void dfs1(int u, int pa) {
fa[u] = pa; deep[u] = deep[pa] + 1;
size[u] = 1;
for(int e = head[u]; e; e = nxt[e]) {
int v = to[e];
if(v == pa) continue;
dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
void dfs2(int u, int pa) {
dfn[u] = ++dfs_clock;
org[dfs_clock] = u;
if(son[u]) {
top[son[u]] = top[u];
dfs2(son[u], u);
}
for(int e = head[u]; e; e = nxt[e]) {
int v = to[e];
if(v == son[u] || v == pa) continue;
top[v] = v;
dfs2(v, u);
}
}
// PartII. Segment
struct Node {
int val;
int color[2];
Node() { val = color[0] = color[1] = 0; }
} node[maxn * 4];
int tag[maxn * 4];
Node inline merge(Node left, Node right)
{
Node ans;
ans.val = left.val + right.val - (left.color[1] == right.color[0]);
ans.color[0] = left.color[0], ans.color[1] = right.color[1];
return ans;
}
void inline pushup(int id) {
node[id] = merge(node[id << 1], node[id << 1 | 1]);
}
void inline pushdown(int id) {
if(tag[id]) {
tag[id << 1] = tag[id << 1 | 1] = tag[id];
node[id << 1].val = node[id << 1 | 1].val = 1;
node[id << 1].color[0] = node[id << 1].color[1] = node[id << 1 | 1].color[0] = node[id << 1 | 1].color[1] = tag[id];
tag[id] = 0;
}
}
void build(int id, int l, int r) {
if(l == r) {
node[id].val = 1, node[id].color[0] = node[id].color[1] = col[org[l]];
return;
}
int mid = l + r >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
pushup(id);
}
Node query(int id, int l, int r, int s, int t) {
if(s <= l && t >= r) {
return node[id];
}
int mid = l + r >> 1;
pushdown(id); Node ansl, ansr;
if(s <= mid) { ansl = query(id << 1, l, mid, s, t); if(t <= mid) return ansl; }
if(t > mid) { ansr = query(id << 1 | 1, mid + 1, r, s, t); if(s > mid) return ansr; }
return merge(ansl, ansr);
}
void rset(int id, int l, int r, int s, int t, int v) {
if(s <= l && t >= r) {
tag[id] = node[id].color[0] = node[id].color[1] = v;
node[id].val = 1;
return;
}
int mid = l + r >> 1;
pushdown(id);
if(s <= mid) rset(id << 1, l, mid, s, t, v);
if(t > mid) rset(id << 1 | 1, mid + 1, r, s ,t ,v);
pushup(id);
}
}
using namespace Tree;
void inline Init()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i) scanf("%d", col + i);
int u, v;
for(int i = 1; i < n; ++i) {
scanf("%d %d", &u, &v);
addEdge(u, v);
}
dfs1(1, 0);
top[1] = 1;
dfs2(1, 0);
build(1, 1, n);
}
char opt[5]; int x, y, v;
void inline Solve()
{
while(m--) {
scanf("%s %d %d", opt, &x, &y);
if(opt[0] == 'C') {
scanf("%d", &v);
while(top[x] != top[y]) {
if(deep[top[x]] < deep[top[y]]) swap(x, y);
rset(1, 1, n, dfn[top[x]], dfn[x], v);
x = fa[top[x]];
}
if(deep[x] > deep[y]) swap(x, y);
rset(1, 1, n, dfn[x], dfn[y], v);
} else {
Node ansl, ansr;
while(top[x] != top[y]) {
if(deep[top[x]] > deep[top[y]]) {
ansl = merge(query(1, 1, n, dfn[top[x]], dfn[x]), ansl);
x = fa[top[x]];
} else {
ansr = merge(query(1, 1, n, dfn[top[y]], dfn[y]), ansr);
y = fa[top[y]];
}
}
if(deep[x] > deep[y]) {
ansl = merge(query(1, 1, n, dfn[y], dfn[x]), ansl);
} else {
ansr = merge(query(1 ,1, n, dfn[x], dfn[y]), ansr);
}
swap(ansl.color[0], ansl.color[1]);
printf("%d
", merge(ansl, ansr).val);
}
}
}
int main()
{
Init();
Solve();
return 0;
}