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)）
参考程序
看起来不大舒服，还是应该写成模板的形式。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> #define V 100008
#define E 200008
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1 int n,m,Q;
int a[V],size[V],dep[V],fa[V],top[V],w[V],son[V],rank[V];
int tag_1[V << ],tag_2[V << ],lazy_1[V << ],lazy_2[V << ]; /*-----------------邻接表---------------*/
struct line{
int u,v,nt;
}eg[E];
int lt[V],summ,cnt; void adt(int u,int v){
eg[++summ].u=u; eg[summ].v=v; eg[summ].nt=lt[u]; lt[u]=summ;
} void add(int u,int v){
adt(u,v); adt(v,u);
}
/*---------------------------------------*/
/*------------------线段树---------------*/
void pushup(int rt){
tag_1[rt]=tag_1[rt<<]+tag_1[rt<<|];
} void pushdown_1(int rt,int m){
if (lazy_1[rt]){
tag_1[rt<<]= (m-m/) - tag_1[rt<<]; // wrong 4
tag_1[rt<<|]= (m/) - tag_1[rt<<|];
lazy_1[rt<<]^=;
lazy_1[rt<<|]^=;
lazy_1[rt]=;
}
} void pushdown_2(int rt){
if (lazy_2[rt]){
tag_2[rt<<]^=;
tag_2[rt<<|]^=;
lazy_2[rt<<]^=;
lazy_2[rt<<|]^=;
lazy_2[rt]=;
}
} void build(int l,int r,int rt){
tag_1[rt]=tag_2[rt]=lazy_1[rt]=lazy_2[rt]=;
if (l==r) return;
int m=(l+r) >> ;
build(lson);
build(rson);
pushup(rt);
} void update_1(int L,int R,int l,int r,int rt){
if (L <= l && r <= R) {
tag_1[rt]=r-l+-tag_1[rt];
lazy_1[rt]^=;
return;
}
pushdown_1(rt,r-l+);
int m = (l + r) >> ;
if (L <= m) update_1(L,R,lson);
if (m < R) update_1(L,R,rson);
pushup(rt); } void update_2(int L,int R,int l,int r,int rt){
if (L <= l && r <= R) {
tag_2[rt]^=;
lazy_2[rt]^=;
return;
}
pushdown_2(rt);
int m = (l + r) >> ;
if (L <= m) update_2(L,R,lson);
if (m < R) update_2(L,R,rson);
} int query_1(int L,int R,int l,int r,int rt){
if (L <= l && r <= R) {
return tag_1[rt];
}
pushdown_1(rt,r - l + );
int m = (l + r) >> ;
int res = ;
if (L <= m) res += query_1(L,R,lson);
if (m < R) res += query_1(L,R,rson);
return res;
} int query_2(int x,int l,int r,int rt){
if (l==r){
return tag_2[rt];
}
pushdown_2(rt);
int m= ( l + r ) >> ;
if (x <= m) return query_2(x,lson);
if (m < x) return query_2(x,rson);
} /*---------------------------------------*/
/*----------------树链剖分---------------*/ void dfs1(int u){
size[u]=; son[u]=;
for (int i=lt[u];i;i=eg[i].nt){
int v=eg[i].v;
if (v!=fa[u]){
fa[v]=u;
dep[v]=dep[u]+;
dfs1(v);
size[u]+=size[v];
if (size[v]>size[son[u]]) son[u]=v;
}
}
} void dfs2(int u,int tp,int x){
top[u]=tp; w[u]=++cnt; rank[cnt]=u;
if (son[u]) dfs2(son[u],tp,);
for (int i=lt[u];i;i=eg[i].nt){
int v=eg[i].v;
if (v==son[u] || v==fa[u]) continue;
dfs2(v,v,);
}
} void init(){
memset(lt,,sizeof(lt));
summ=; cnt=;
scanf("%d",&n);
for (int i=;i<n;i++){
int u,v;
scanf("%d %d",&u,&v);
add(u,v);
}
dep[]=; fa[]=;
dfs1();
dfs2(,,);
build(,n,);
}
/*---------------------------------------*/
void work_1(int x,int y){
while (top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) std::swap(x,y);
update_1(w[top[x]],w[x],,n,);
x=fa[top[x]];
}
if (dep[x]>dep[y]) std::swap(x,y);
update_1(w[x]+,w[y],,n,); //wrong 2
} void work_2(int x,int y){
while (top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) std::swap(x,y);
update_2(w[top[x]],w[x],,n,);
if (son[x]) update_1(w[son[x]],w[son[x]],,n,);
if (son[fa[top[x]]]==top[x]) update_1(w[top[x]],w[top[x]],,n,);
x=fa[top[x]];
}
if (dep[x]>dep[y]) std::swap(x,y);
update_2(w[x],w[y],,n,);
if (son[y]) update_1(w[son[y]],w[son[y]],,n,);
if (son[fa[x]]==x) update_1(w[x],w[x],,n,);
} void work_3(int x,int y){
int res=;
while (top[x]!=top[y]){
if (dep[top[x]]<dep[top[y]]) std::swap(x,y);
res+=query_1(w[top[x]]+,w[x],,n,); //wrong 3
res+=query_1(w[top[x]],w[top[x]],,n,) ^ query_2(w[top[x]],,n,) ^ query_2(w[fa[top[x]]],,n,);
x=fa[top[x]];
}
if (dep[x]>dep[y]) std::swap(x,y);;
res+=query_1(w[x]+,w[y],,n,);
printf("%d\n",res);
} int main(){
int T;
scanf("%d",&T);
while (T--){
init();
scanf("%d",&Q);
while (Q--){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
if (x==) work_1(y,z);
if (x==) work_2(y,z);
if (x==) work_3(y,z);
}
}
}