就是个模板啦
记录每一个点的左端点颜色和右端点颜色和当前端点颜色段数。
合并时如果左孩子右端点和右孩子左端点不同就 ans--
在重链上跳的时候别忘记统计一下
——代码
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 400001
#define ls now << 1
#define rs now << 1 | 1
#define swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
#define pushup(now) Lcol[now] = Lcol[ls], Rcol[now] = Rcol[rs], col[now] = col[ls] + col[rs] - (Rcol[ls] == Lcol[rs])
int n, m, cnt, tim;
int head[N], to[N << 1], next[N << 1];
int a[N], f[N], deep[N], size[N], son[N], tid[N], top[N], rank[N], L[N], R[N], Lcol[N], Rcol[N], col[N], laz[N];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
}
inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
}
inline void dfs1(int u)
{
int i, v;
size[u] = 1;
deep[u] = deep[f[u]] + 1;
for(i = head[u]; i ^ -1; i = next[i])
{
v = to[i];
if(v ^ f[u])
{
f[v] = u;
dfs1(v);
size[u] += size[v];
if(son[u] == -1 || size[son[u]] < size[v]) son[u] = v;
}
}
}
inline void dfs2(int u, int t)
{
int i, v;
top[u] = t;
tid[u] = ++tim;
rank[tim] = u;
if(son[u] == -1) return;
dfs2(son[u], t);
for(i = head[u]; i ^ -1; i = next[i])
{
v = to[i];
if(v ^ f[u] && v ^ son[u]) dfs2(v, v);
}
}
inline void build(int now, int l, int r)
{
L[now] = l;
R[now] = r;
if(l == r)
{
col[now] = 1;
Lcol[now] = Rcol[now] = a[rank[l]];
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(now);
}
inline void pushdown(int now)
{
if(laz[now])
{
col[ls] = col[rs] = 1;
laz[ls] = laz[rs] = Lcol[ls] = Lcol[rs] = Rcol[ls] = Rcol[rs] = laz[now];
laz[now] = 0;
}
}
inline void update(int now, int l, int r, int z)
{
if(l <= L[now] && R[now] <= r)
{
col[now] = 1;
laz[now] = Lcol[now] = Rcol[now] = z;
return;
}
pushdown(now);
int mid = (L[now] + R[now]) >> 1;
if(l <= mid) update(ls, l, r, z);
if(mid < r) update(rs, l, r, z);
pushup(now);
}
inline void q_update(int u, int v, int z)
{
while(top[u] ^ top[v])
{
if(deep[top[u]] < deep[top[v]]) swap(u, v);
update(1, tid[top[u]], tid[u], z);
u = f[top[u]];
}
if(deep[u] > deep[v]) swap(u, v);
update(1, tid[u], tid[v], z);
}
inline int q_color(int now, int x)
{
if(L[now] == R[now]) return Lcol[now];
pushdown(now);
int mid = (L[now] + R[now]) >> 1;
if(x <= mid) return q_color(ls, x);
else return q_color(rs, x);
}
inline int query(int now, int l, int r)
{
if(l <= L[now] && R[now] <= r) return col[now];
pushdown(now);
int mid = (L[now] + R[now]) >> 1, ans = 0;
if(l <= mid) ans += query(ls, l, r);
if(mid < r) ans += query(rs, l, r);
if(l <= mid && mid < r) ans -= (Rcol[ls] == Lcol[rs]);
return ans;
}
inline int q_query(int u, int v)
{
int ans = 0;
while(top[u] ^ top[v])
{
if(deep[top[u]] < deep[top[v]]) swap(u, v);
ans += query(1, tid[top[u]], tid[u]);
ans -= (q_color(1, tid[f[top[u]]]) == q_color(1, tid[top[u]]));
u = f[top[u]];
}
if(deep[u] > deep[v]) swap(u, v);
ans += query(1, tid[u], tid[v]);
return ans;
}
int main()
{
int i, x, y, z;
char s[10];
n = read();
m = read();
memset(son, -1, sizeof(son));
memset(head, -1, sizeof(head));
for(i = 1; i <= n; i++) a[i] = read();
for(i = 1; i < n; i++)
{
x = read();
y = read();
add(x, y);
add(y, x);
}
dfs1(1);
dfs2(1, 1);
build(1, 1, n);
for(i = 1; i <= m; i++)
{
scanf("%s", s);
x = read();
y = read();
if(s[0] == 'C')
{
z = read();
q_update(x, y, z);
}
else printf("%d
", q_query(x, y));
}
return 0;
}