LCT的一种姿势。
题意：给定一棵树。每次把一条路径上的点染成一种颜色，求一条路径上有多少段颜色。
解：
首先可以很轻易的用树剖解决，只不过代码量让人望而却步...
有一种难以想象的LCT做法...
记录每个点的颜色，修改用lazy tag
询问时把那一条链split出来，pushup的时候看当前点和前驱/后继的颜色是否相同。如果不同就sum++，表示有一条连接不同颜色点的边。
最后的sum就是连接不同颜色的点的边数，再加1就是段数了。
#include <cstdio>
#include <algorithm> const int N = ; int fa[N], s[N][], col[N], sum[N], lc[N], rc[N], S[N], Sp, tag[N];
bool rev[N]; inline bool no_root(int x) {
return (s[fa[x]][] == x) || (s[fa[x]][] == x);
} inline void pushdown(int x) {
int ls = s[x][], rs = s[x][];
if(rev[x]) {
if(ls) {
rev[ls] ^= ;
std::swap(lc[ls], rc[ls]);
}
if(rs) {
rev[rs] ^= ;
std::swap(lc[rs], rc[rs]);
}
std::swap(s[x][], s[x][]);
rev[x] = ;
}
if(tag[x]) {
int c = tag[x];
if(ls) {
tag[ls] = col[ls] = lc[ls] = rc[ls] = c;
sum[ls] = ;
}
if(rs) {
tag[rs] = col[rs] = lc[rs] = rc[rs] = c;
sum[rs] = ;
}
tag[x] = ;
}
return;
} inline void pushup(int x) {
int ls = s[x][], rs = s[x][];
pushdown(ls);
pushdown(rs);
sum[x] = sum[ls] + sum[rs];
if(ls) {
lc[x] = lc[ls];
if(rc[ls] != col[x]) {
sum[x]++;
}
}
else {
lc[x] = col[x];
}
if(rs) {
rc[x] = rc[rs];
if(lc[rs] != col[x]) {
sum[x]++;
}
}
else {
rc[x] = col[x];
}
return;
} inline void rotate(int x) {
int y = fa[x];
int z = fa[y];
bool f = (s[y][] == x); fa[x] = z;
if(no_root(y)) {
s[z][s[z][] == y] = x;
}
s[y][f] = s[x][!f];
if(s[x][!f]) {
fa[s[x][!f]] = y;
}
s[x][!f] = y;
fa[y] = x; pushup(y);
pushup(x);
return;
} inline void splay(int x) {
int y = x;
S[++Sp] = y;
while(no_root(y)) {
y = fa[y];
S[++Sp] = y;
}
while(Sp) {
pushdown(S[Sp]);
Sp--;
} y = fa[x];
int z = fa[y];
while(no_root(x)) {
if(no_root(y)) {
(s[z][] == y) ^ (s[y][] == x) ?
rotate(x) : rotate(y);
}
rotate(x);
y = fa[x];
z = fa[y];
}
return;
} inline void access(int x) {
int y = ;
while(x) {
splay(x);
s[x][] = y;
pushup(x);
y = x;
x = fa[x];
}
return;
} inline void make_root(int x) {
access(x);
splay(x);
rev[x] = ;
return;
} inline int find_root(int x) {
access(x);
splay(x);
while(s[x][]) {
x = s[x][];
pushdown(x);
}
return x;
} inline void link(int x, int y) {
make_root(x);
fa[x] = y;
return;
} inline void cut(int x, int y) {
make_root(x);
access(y);
splay(y);
fa[x] = s[y][] = ;
pushup(y);
return;
} inline void change(int x, int y, int c) {
make_root(x);
access(y);
splay(y);
tag[y] = col[y] = lc[y] = rc[y] = c;
sum[y] = ;
return;
} inline int ask(int x, int y) {
make_root(x);
access(y);
splay(y);
return sum[y] + ;
} char str[]; int main() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%d", &col[i]);
lc[i] = rc[i] = col[i];
}
for(int i = , x, y; i < n; i++) {
scanf("%d%d", &x, &y);
link(x, y);
} for(int i = , x, y, z; i <= m; i++) {
scanf("%s%d%d", str, &x, &y);
if(str[] == 'C') {
scanf("%d", &z);
change(x, y, z);
}
else {
int t = ask(x, y);
printf("%d\n", t);
}
} return ;
}
AC代码
有个简化版的问题：给定根，每次修改/询问必有一端点是根。有一种解法是，染色access，查询就看要跳多少个虚边。但是这样会被链卡成n²...不知道怎么改进。