Problem Little Devil I （HDU4897）
题目大意
给定一棵树，每条边的颜色为黑或白，起始时均为白。
支持3种操作：
操作1：将a->b的路径中的所有边的颜色翻转。
操作2：将所有 有且仅有一个点在a->b的路径中 的边的颜色翻转。
操作3：询问a->b的路径中的黑色边数量。
解题分析
考虑操作1，只需正常的树链剖分+线段树维护即可。用线段树维护每条边，tag_1[i]表示该区间中的黑色边数量。
考虑操作2，一个节点相邻的边只可能为重链和轻链，且重链的数目小于等于2。故对于重链每次直接修改。对于轻链，则需要再用一棵线段树来维护每个节点，tag_2[i]表示该点所连接的所有轻链是否需要被翻转。
考虑操作3，一条路径中的重链的信息均已存至第一棵线段树中，直接查询即可。对于轻链，还取决于该边的两个端点是否进行过操作2，用tag_2异或一下即可。
eg：轻链a->b ,则该链的颜色为tag_1[a->b] ^ tag_2[a] ^ tag_2[b]
简要做法：
操作1：每次修改一条重链和重链上方的一条轻链，表示这些链的颜色被翻转。
操作2：每次直接修改一条重链上下方的重链，每个节点记录是否翻转。
操作3：重链直接查询，轻链异或求得。
时间复杂度（Qlog2(n)）
参考程序
看起来不大舒服，还是应该写成模板的形式。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 6 #define V 100008 7 #define E 200008 8 #define lson l,m,rt<<1 9 #define rson m+1,r,rt<<1|1 10 11 int n,m,Q; 12 int a[V],size[V],dep[V],fa[V],top[V],w[V],son[V],rank[V]; 13 int tag_1[V << 2],tag_2[V << 2],lazy_1[V << 2],lazy_2[V << 2]; 14 15 /*-----------------邻接表---------------*/ 16 struct line{ 17 int u,v,nt; 18 }eg[E]; 19 int lt[V],summ,cnt; 20 21 void adt(int u,int v){ 22 eg[++summ].u=u; eg[summ].v=v; eg[summ].nt=lt[u]; lt[u]=summ; 23 } 24 25 void add(int u,int v){ 26 adt(u,v); adt(v,u); 27 } 28 /*---------------------------------------*/ 29 /*------------------线段树---------------*/ 30 void pushup(int rt){ 31 tag_1[rt]=tag_1[rt<<1]+tag_1[rt<<1|1]; 32 } 33 34 void pushdown_1(int rt,int m){ 35 if (lazy_1[rt]){ 36 tag_1[rt<<1]= (m-m/2) - tag_1[rt<<1]; // wrong 4 37 tag_1[rt<<1|1]= (m/2) - tag_1[rt<<1|1]; 38 lazy_1[rt<<1]^=1; 39 lazy_1[rt<<1|1]^=1; 40 lazy_1[rt]=0; 41 } 42 } 43 44 void pushdown_2(int rt){ 45 if (lazy_2[rt]){ 46 tag_2[rt<<1]^=1; 47 tag_2[rt<<1|1]^=1; 48 lazy_2[rt<<1]^=1; 49 lazy_2[rt<<1|1]^=1; 50 lazy_2[rt]=0; 51 } 52 } 53 54 void build(int l,int r,int rt){ 55 tag_1[rt]=tag_2[rt]=lazy_1[rt]=lazy_2[rt]=0; 56 if (l==r) return; 57 int m=(l+r) >> 1; 58 build(lson); 59 build(rson); 60 pushup(rt); 61 } 62 63 void update_1(int L,int R,int l,int r,int rt){ 64 if (L <= l && r <= R) { 65 tag_1[rt]=r-l+1-tag_1[rt]; 66 lazy_1[rt]^=1; 67 return; 68 } 69 pushdown_1(rt,r-l+1); 70 int m = (l + r) >> 1; 71 if (L <= m) update_1(L,R,lson); 72 if (m < R) update_1(L,R,rson); 73 pushup(rt); 74 75 } 76 77 void update_2(int L,int R,int l,int r,int rt){ 78 if (L <= l && r <= R) { 79 tag_2[rt]^=1; 80 lazy_2[rt]^=1; 81 return; 82 } 83 pushdown_2(rt); 84 int m = (l + r) >> 1; 85 if (L <= m) update_2(L,R,lson); 86 if (m < R) update_2(L,R,rson); 87 } 88 89 int query_1(int L,int R,int l,int r,int rt){ 90 if (L <= l && r <= R) { 91 return tag_1[rt]; 92 } 93 pushdown_1(rt,r - l + 1); 94 int m = (l + r) >> 1; 95 int res = 0; 96 if (L <= m) res += query_1(L,R,lson); 97 if (m < R) res += query_1(L,R,rson); 98 return res; 99 } 100 101 int query_2(int x,int l,int r,int rt){ 102 if (l==r){ 103 return tag_2[rt]; 104 } 105 pushdown_2(rt); 106 int m= ( l + r ) >> 1; 107 if (x <= m) return query_2(x,lson); 108 if (m < x) return query_2(x,rson); 109 } 110 111 /*---------------------------------------*/ 112 /*----------------树链剖分---------------*/ 113 114 void dfs1(int u){ 115 size[u]=1; son[u]=0; 116 for (int i=lt[u];i;i=eg[i].nt){ 117 int v=eg[i].v; 118 if (v!=fa[u]){ 119 fa[v]=u; 120 dep[v]=dep[u]+1; 121 dfs1(v); 122 size[u]+=size[v]; 123 if (size[v]>size[son[u]]) son[u]=v; 124 } 125 } 126 } 127 128 void dfs2(int u,int tp,int x){ 129 top[u]=tp; w[u]=++cnt; rank[cnt]=u; 130 if (son[u]) dfs2(son[u],tp,1); 131 for (int i=lt[u];i;i=eg[i].nt){ 132 int v=eg[i].v; 133 if (v==son[u] || v==fa[u]) continue; 134 dfs2(v,v,2); 135 } 136 } 137 138 void init(){ 139 memset(lt,0,sizeof(lt)); 140 summ=1; cnt=0; 141 scanf("%d",&n); 142 for (int i=1;i<n;i++){ 143 int u,v; 144 scanf("%d %d",&u,&v); 145 add(u,v); 146 } 147 dep[1]=1; fa[1]=0; 148 dfs1(1); 149 dfs2(1,1,1); 150 build(1,n,1); 151 } 152 /*---------------------------------------*/ 153 void work_1(int x,int y){ 154 while (top[x]!=top[y]){ 155 if (dep[top[x]]<dep[top[y]]) std::swap(x,y); 156 update_1(w[top[x]],w[x],1,n,1); 157 x=fa[top[x]]; 158 } 159 if (dep[x]>dep[y]) std::swap(x,y); 160 update_1(w[x]+1,w[y],1,n,1); //wrong 2 161 } 162 163 void work_2(int x,int y){ 164 while (top[x]!=top[y]){ 165 if (dep[top[x]]<dep[top[y]]) std::swap(x,y); 166 update_2(w[top[x]],w[x],1,n,1); 167 if (son[x]) update_1(w[son[x]],w[son[x]],1,n,1); 168 if (son[fa[top[x]]]==top[x]) update_1(w[top[x]],w[top[x]],1,n,1); 169 x=fa[top[x]]; 170 } 171 if (dep[x]>dep[y]) std::swap(x,y); 172 update_2(w[x],w[y],1,n,1); 173 if (son[y]) update_1(w[son[y]],w[son[y]],1,n,1); 174 if (son[fa[x]]==x) update_1(w[x],w[x],1,n,1); 175 } 176 177 void work_3(int x,int y){ 178 int res=0; 179 while (top[x]!=top[y]){ 180 if (dep[top[x]]<dep[top[y]]) std::swap(x,y); 181 res+=query_1(w[top[x]]+1,w[x],1,n,1); //wrong 3 182 res+=query_1(w[top[x]],w[top[x]],1,n,1) ^ query_2(w[top[x]],1,n,1) ^ query_2(w[fa[top[x]]],1,n,1); 183 x=fa[top[x]]; 184 } 185 if (dep[x]>dep[y]) std::swap(x,y);; 186 res+=query_1(w[x]+1,w[y],1,n,1); 187 printf("%d ",res); 188 } 189 190 int main(){ 191 int T; 192 scanf("%d",&T); 193 while (T--){ 194 init(); 195 scanf("%d",&Q); 196 while (Q--){ 197 int x,y,z; 198 scanf("%d %d %d",&x,&y,&z); 199 if (x==1) work_1(y,z); 200 if (x==2) work_2(y,z); 201 if (x==3) work_3(y,z); 202 } 203 } 204 }