LCT的一种姿势。
题意：给定一棵树。每次把一条路径上的点染成一种颜色，求一条路径上有多少段颜色。
解：
首先可以很轻易的用树剖解决，只不过代码量让人望而却步...
有一种难以想象的LCT做法...
记录每个点的颜色，修改用lazy tag
询问时把那一条链split出来，pushup的时候看当前点和前驱/后继的颜色是否相同。如果不同就sum++，表示有一条连接不同颜色点的边。
最后的sum就是连接不同颜色的点的边数，再加1就是段数了。
1 #include <cstdio> 2 #include <algorithm> 3 4 const int N = 100010; 5 6 int fa[N], s[N][2], col[N], sum[N], lc[N], rc[N], S[N], Sp, tag[N]; 7 bool rev[N]; 8 9 inline bool no_root(int x) { 10 return (s[fa[x]][0] == x) || (s[fa[x]][1] == x); 11 } 12 13 inline void pushdown(int x) { 14 int ls = s[x][0], rs = s[x][1]; 15 if(rev[x]) { 16 if(ls) { 17 rev[ls] ^= 1; 18 std::swap(lc[ls], rc[ls]); 19 } 20 if(rs) { 21 rev[rs] ^= 1; 22 std::swap(lc[rs], rc[rs]); 23 } 24 std::swap(s[x][0], s[x][1]); 25 rev[x] = 0; 26 } 27 if(tag[x]) { 28 int c = tag[x]; 29 if(ls) { 30 tag[ls] = col[ls] = lc[ls] = rc[ls] = c; 31 sum[ls] = 0; 32 } 33 if(rs) { 34 tag[rs] = col[rs] = lc[rs] = rc[rs] = c; 35 sum[rs] = 0; 36 } 37 tag[x] = 0; 38 } 39 return; 40 } 41 42 inline void pushup(int x) { 43 int ls = s[x][0], rs = s[x][1]; 44 pushdown(ls); 45 pushdown(rs); 46 sum[x] = sum[ls] + sum[rs]; 47 if(ls) { 48 lc[x] = lc[ls]; 49 if(rc[ls] != col[x]) { 50 sum[x]++; 51 } 52 } 53 else { 54 lc[x] = col[x]; 55 } 56 if(rs) { 57 rc[x] = rc[rs]; 58 if(lc[rs] != col[x]) { 59 sum[x]++; 60 } 61 } 62 else { 63 rc[x] = col[x]; 64 } 65 return; 66 } 67 68 inline void rotate(int x) { 69 int y = fa[x]; 70 int z = fa[y]; 71 bool f = (s[y][1] == x); 72 73 fa[x] = z; 74 if(no_root(y)) { 75 s[z][s[z][1] == y] = x; 76 } 77 s[y][f] = s[x][!f]; 78 if(s[x][!f]) { 79 fa[s[x][!f]] = y; 80 } 81 s[x][!f] = y; 82 fa[y] = x; 83 84 pushup(y); 85 pushup(x); 86 return; 87 } 88 89 inline void splay(int x) { 90 int y = x; 91 S[++Sp] = y; 92 while(no_root(y)) { 93 y = fa[y]; 94 S[++Sp] = y; 95 } 96 while(Sp) { 97 pushdown(S[Sp]); 98 Sp--; 99 } 100 101 y = fa[x]; 102 int z = fa[y]; 103 while(no_root(x)) { 104 if(no_root(y)) { 105 (s[z][1] == y) ^ (s[y][1] == x) ? 106 rotate(x) : rotate(y); 107 } 108 rotate(x); 109 y = fa[x]; 110 z = fa[y]; 111 } 112 return; 113 } 114 115 inline void access(int x) { 116 int y = 0; 117 while(x) { 118 splay(x); 119 s[x][1] = y; 120 pushup(x); 121 y = x; 122 x = fa[x]; 123 } 124 return; 125 } 126 127 inline void make_root(int x) { 128 access(x); 129 splay(x); 130 rev[x] = 1; 131 return; 132 } 133 134 inline int find_root(int x) { 135 access(x); 136 splay(x); 137 while(s[x][0]) { 138 x = s[x][0]; 139 pushdown(x); 140 } 141 return x; 142 } 143 144 inline void link(int x, int y) { 145 make_root(x); 146 fa[x] = y; 147 return; 148 } 149 150 inline void cut(int x, int y) { 151 make_root(x); 152 access(y); 153 splay(y); 154 fa[x] = s[y][0] = 0; 155 pushup(y); 156 return; 157 } 158 159 inline void change(int x, int y, int c) { 160 make_root(x); 161 access(y); 162 splay(y); 163 tag[y] = col[y] = lc[y] = rc[y] = c; 164 sum[y] = 0; 165 return; 166 } 167 168 inline int ask(int x, int y) { 169 make_root(x); 170 access(y); 171 splay(y); 172 return sum[y] + 1; 173 } 174 175 char str[10]; 176 177 int main() { 178 int n, m; 179 scanf("%d%d", &n, &m); 180 for(int i = 1; i <= n; i++) { 181 scanf("%d", &col[i]); 182 lc[i] = rc[i] = col[i]; 183 } 184 for(int i = 1, x, y; i < n; i++) { 185 scanf("%d%d", &x, &y); 186 link(x, y); 187 } 188 189 for(int i = 1, x, y, z; i <= m; i++) { 190 scanf("%s%d%d", str, &x, &y); 191 if(str[0] == 'C') { 192 scanf("%d", &z); 193 change(x, y, z); 194 } 195 else { 196 int t = ask(x, y); 197 printf("%d ", t); 198 } 199 } 200 201 return 0; 202 }
有个简化版的问题：给定根，每次修改/询问必有一端点是根。有一种解法是，染色access，查询就看要跳多少个虚边。但是这样会被链卡成n²...不知道怎么改进。