定位:中等题 LCT和树链剖分都可以做,简单起见就说说树链剖分,LCT类似。
首先注意到一条路径上是log n条重链和log n条轻边。
当我们给一个点的所有边上的邻居边打标记时,如果该点在重链上,会影响他的轻孩子们。(要特殊考虑链头和链尾之类的)。
那么我们可以给重链上的点打标记,表示这个点的轻孩子们被翻转了没。
那么一个轻边就可以直接询问出来。复杂度:O(n(logn)^2)。
这个官方题解不怎么详细,我说一下我的解法:
首先跟普通的树链剖分一样,先给每个结点编上一个编号,每条重链用一个线段树来维护(其实都放到同一个线段树中了,占用不同的位置)
现在用线段树维护3个值:sum代表这个区间的黑边总数,flip代表这个区间的边是否被翻转颜色,light代表这个区间是否被打上了翻转标记(后面再说这个是啥)
其中所有边的编号为其靠下方的结点的编号,也就是根的编号在边的维护中没有意义
其中light代表这个点作为操作②所影响的次数,即它的轻边(不考虑与父节点的边)被翻转次数的奇偶。
维护这些值,考虑重链上的重边,某条边是黑色当且仅当它在线段树中的flip是1(被翻转了奇数次)。而对于不在重链上的边,它是黑色当且仅当它在线段树中的flip(被翻转的次数奇偶性)和它的父亲被打上翻转标记的次数light的和是奇数(异或值为1)。
那么,对于操作①,在树链往上走的时候,把所有边都翻转一次即可,没有什么难度。
对于操作②,在树链往上走的时候,除了要给所有路径上的点打上翻转标记以外,还要:翻转重链上的孩纸边,因为它要翻转而不受翻转标记的影响;翻转重链的父边,它是轻边,会受到重链的父亲的翻转标记的影响,所以直接给翻转一次抵消这种影响。
对于操作③,在树链往上走的时候,统计重链上的黑边和sum,和不在重链上的黑边(上面有讲)。
然后这样就差写代码了。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 typedef long long LL; 7 8 const int MAXV = 100010; 9 const int MAXE = MAXV << 1; 10 const int MAXT = MAXV << 2; 11 12 int head[MAXV], ecnt; 13 int to[MAXE], next[MAXE]; 14 int n, m, T; 15 //Graph 16 void initGraph() { 17 memset(head + 1, -1, n * sizeof(int)); 18 ecnt = 0; 19 } 20 21 void add_edge(int u, int v) { 22 to[ecnt] = v; next[ecnt] = head[u]; head[u] = ecnt++; 23 to[ecnt] = u; next[ecnt] = head[v]; head[v] = ecnt++; 24 } 25 //Segment Tree 26 #define ll (x << 1) 27 #define rr (ll | 1) 28 #define mid ((l + r) >> 1) 29 int sum[MAXT], flip[MAXT]; 30 int light[MAXT];//轻边是否翻转 31 32 void initSegmentTree() { 33 memset(sum + 1, 0, 4 * n * sizeof(int)); 34 memset(flip + 1, 0, 4 * n * sizeof(int)); 35 memset(light + 1, 0, 4 * n * sizeof(int)); 36 } 37 38 void pushdown(int x, int l, int r) { 39 if(flip[x]) { 40 flip[ll] ^= 1; 41 sum[ll] = (mid - l + 1) - sum[ll]; 42 flip[rr] ^= 1; 43 sum[rr] = (r - mid) - sum[rr]; 44 flip[x] = 0; 45 } 46 if(light[x]) { 47 light[ll] ^= 1; 48 light[rr] ^= 1; 49 light[x] = 0; 50 } 51 } 52 53 void maintain(int x) { 54 sum[x] = sum[ll] + sum[rr]; 55 } 56 57 void modifyFlip(int x, int l, int r, int a, int b) { 58 if(a <= l && r <= b) { 59 flip[x] ^= 1; 60 sum[x] = (r - l + 1) - sum[x]; 61 } else { 62 pushdown(x, l, r); 63 if(a <= mid) modifyFlip(ll, l, mid, a, b); 64 if(mid < b) modifyFlip(rr, mid + 1, r, a, b); 65 maintain(x); 66 } 67 } 68 69 void modifyLight(int x, int l, int r, int a, int b) { 70 if(a <= l && r <= b) { 71 light[x] ^= 1; 72 } else { 73 pushdown(x, l, r); 74 if(a <= mid) modifyLight(ll, l, mid, a, b); 75 if(mid < b) modifyLight(rr, mid + 1, r, a, b); 76 } 77 } 78 79 int queryFlip(int x, int l, int r, int a, int b) { 80 if(a <= l && r <= b) { 81 return sum[x]; 82 } else { 83 int res = 0; 84 pushdown(x, l, r); 85 if(a <= mid) res += queryFlip(ll, l, mid, a, b); 86 if(mid < b) res += queryFlip(rr, mid + 1, r, a, b); 87 return res; 88 } 89 } 90 91 int queryLight(int x, int l, int r, int a, int b) { 92 if(a <= l && r <= b) { 93 return light[x]; 94 } else { 95 int res = 0; 96 pushdown(x, l, r); 97 if(a <= mid) res += queryLight(ll, l, mid, a, b); 98 if(mid < b) res += queryLight(rr, mid + 1, r, a, b); 99 return res;100 }101 }102 //树链剖分103 int fa[MAXV], size[MAXV], son[MAXV], top[MAXV], tid[MAXV], dep[MAXV];104 int dfs_clock;105 106 void dfs_size(int u, int f, int depth) {107 fa[u] = f; dep[u] = depth;108 size[u] = 1; son[u] = 0;109 int maxsize = 0;110 for(int p = head[u]; ~p; p = next[p]) {111 int &v = to[p];112 if(v == f) continue;113 dfs_size(v, u, depth + 1);114 size[u] += size[v];115 if(size[v] > maxsize) {116 son[u] = v;117 maxsize = size[v];118 }119 }120 }121 122 void dfs_heavy_edge(int u, int ancestor) {123 tid[u] = ++dfs_clock; top[u] = ancestor;124 if(son[u]) dfs_heavy_edge(son[u], ancestor);125 for(int p = head[u]; ~p; p = next[p]) {126 int &v = to[p];127 if(v == fa[u] || v == son[u]) continue;128 dfs_heavy_edge(v, v);129 }130 }131 132 void modifyFlip(int a, int b) {133 while(top[a] != top[b]) {134 if(dep[top[a]] < dep[top[b]]) swap(a, b);135 modifyFlip(1, 1, n, tid[top[a]], tid[a]);136 a = fa[top[a]];137 }138 if(a != b) {139 if(dep[a] < dep[b]) swap(a, b);140 modifyFlip(1, 1, n, tid[son[b]], tid[a]);141 }142 }143 144 void modifyLight(int a, int b) {145 while(top[a] != top[b]) {146 if(dep[top[a]] < dep[top[b]]) swap(a, b);147 modifyLight(1, 1, n, tid[top[a]], tid[a]);148 if(son[a]) modifyFlip(1, 1, n, tid[son[a]], tid[son[a]]);149 modifyFlip(1, 1, n, tid[top[a]], tid[top[a]]);150 a = fa[top[a]];151 }152 if(dep[a] < dep[b]) swap(a, b);153 modifyLight(1, 1, n, tid[b], tid[a]);154 if(fa[b]) modifyFlip(1, 1, n, tid[b], tid[b]);155 if(son[a]) modifyFlip(1, 1, n, tid[son[a]], tid[son[a]]);156 }157 158 int query(int a, int b) {159 int res = 0;160 while(top[a] != top[b]) {161 if(dep[top[a]] < dep[top[b]]) swap(a, b);162 if(a != top[a]) res += queryFlip(1, 1, n, tid[son[top[a]]], tid[a]);163 res += queryFlip(1, 1, n, tid[top[a]], tid[top[a]]) ^ queryLight(1, 1, n, tid[fa[top[a]]], tid[fa[top[a]]]);164 a = fa[top[a]];165 }166 if(a != b) {167 if(dep[a] < dep[b]) swap(a, b);168 res += queryFlip(1, 1, n, tid[son[b]], tid[a]);169 }170 return res;171 }172 173 void ask() {174 int a, b;175 while(cin>>a>>b && a + b) {176 cout<