題目大意：

給一棵樹，每條邊可能是黑色或白色(起始都是白色)，有三種操作：

1、將u到v路徑上所有邊顏色翻轉(zhuǎn)(黑->白，白->黑)

2、將只有一個點在u到v路徑上的邊顏色翻轉(zhuǎn)

3、查詢u到v路徑上顏色為黑色的邊數(shù)

?

如果只有1、3操作很好做，直接樹鏈剖分+線段樹，重點是2操作(廢話)。

可以發(fā)現(xiàn)只有l(wèi)ca需要翻轉(zhuǎn)和它父節(jié)點之間的邊，因此將這條邊暴力翻轉(zhuǎn)。

現(xiàn)在剩下需要翻轉(zhuǎn)的就是u到v路徑上所有點與他們子節(jié)點之間的邊。

我們將u到v的路徑分成若干條重鏈，可以發(fā)現(xiàn)每條重鏈除了鏈低端的那個點，其他點要反轉(zhuǎn)的是他們與他們所有輕兒子之間的邊(這里注意特判l(wèi)ca少翻轉(zhuǎn)了一條輕邊)。

這么多邊顯然不能都翻轉(zhuǎn)，那么我們再開一棵線段樹，將重鏈上的點打標(biāo)記，代表這些點與他們所有輕兒子之間的邊需要翻轉(zhuǎn)。

至于重鏈低端那個點還要暴力翻轉(zhuǎn)它與重兒子間的邊。

但現(xiàn)在只處理了每條重鏈，沒有考慮兩條鏈之間連接的那條邊?

假設(shè)y鏈接在x鏈下面，那么x鏈低端那個點需要翻轉(zhuǎn)的是除了一個輕邊之外的其他輕邊和一條重邊，那么只需要將重邊和不需要翻轉(zhuǎn)的輕邊翻轉(zhuǎn)之后再打標(biāo)記就好了。

將邊下傳到點，開兩棵線段樹，一棵維護(hù)邊的顏色，另一棵維護(hù)給輕兒子翻轉(zhuǎn)的標(biāo)記(這棵線段樹建議標(biāo)記永久化)，每次修改時注意鏈與鏈之間輕邊的翻轉(zhuǎn)即可。

#include<set> #include<map> #include<stack> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int T; int n,m; int x,y; int tot; int opt; int num; int a[800010]; int b[800010]; int d[100010]; int f[100010]; int s[100010]; int to[200010]; int sum[800010]; int son[100010]; int top[100010]; int size[100010]; int head[100010]; int next[200010]; void add(int x,int y) {tot++;next[tot]=head[x];head[x]=tot;to[tot]=y; } void dfs(int x) {d[x]=d[f[x]]+1;size[x]=1;for(int i=head[x];i;i=next[i]){if(to[i]!=f[x]){f[to[i]]=x;dfs(to[i]);size[x]+=size[to[i]];if(size[to[i]]>size[son[x]]){son[x]=to[i];}}} } void dfs2(int x,int tp) {s[x]=++num;top[x]=tp;if(son[x]){dfs2(son[x],tp);}for(int i=head[x];i;i=next[i]){if(to[i]!=f[x]&&to[i]!=son[x]){dfs2(to[i],to[i]);}} } void updata(int rt,int l,int r,int L,int R) {if(L<=l&&r<=R){b[rt]^=1;return ;}int mid=(l+r)>>1;if(L<=mid){updata(rt<<1,l,mid,L,R);}if(R>mid){updata(rt<<1|1,mid+1,r,L,R);} } int downdata(int rt,int l,int r,int k) {if(l==r){return b[rt];}int res=b[rt];int mid=(l+r)>>1;if(k<=mid){return res^downdata(rt<<1,l,mid,k);}else{return res^downdata(rt<<1|1,mid+1,r,k);} } void pushup(int rt) {sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void pushdown(int rt,int l,int r) {if(a[rt]){int mid=(l+r)>>1;a[rt<<1]^=1;a[rt<<1|1]^=1;sum[rt<<1]=(mid-l+1)-sum[rt<<1];sum[rt<<1|1]=(r-mid)-sum[rt<<1|1];a[rt]=0;} } void change1(int rt,int l,int r,int k) {if(l==r){sum[rt]^=1;return ;}pushdown(rt,l,r);int mid=(l+r)>>1;if(k<=mid){change1(rt<<1,l,mid,k);}else{change1(rt<<1|1,mid+1,r,k);}pushup(rt); } void change2(int rt,int l,int r,int L,int R) {if(L<=l&&r<=R){a[rt]^=1;sum[rt]=(r-l+1)-sum[rt];return ;}pushdown(rt,l,r);int mid=(l+r)>>1;if(L<=mid){change2(rt<<1,l,mid,L,R);}if(R>mid){change2(rt<<1|1,mid+1,r,L,R);}pushup(rt); } int query1(int rt,int l,int r,int k) {if(l==r){return sum[rt];}pushdown(rt,l,r);int mid=(l+r)>>1;if(k<=mid){return query1(rt<<1,l,mid,k);}else{return query1(rt<<1|1,mid+1,r,k);} } int query2(int rt,int l,int r,int L,int R) {if(L<=l&&r<=R){return sum[rt];}pushdown(rt,l,r);int mid=(l+r)>>1;int res=0;if(L<=mid){res+=query2(rt<<1,l,mid,L,R);}if(R>mid){res+=query2(rt<<1|1,mid+1,r,L,R);}return res; } void rotate1(int x,int y) {while(top[x]!=top[y]){if(d[top[x]]<d[top[y]]){swap(x,y);}change2(1,1,n,s[top[x]],s[x]);x=f[top[x]];}if(d[x]>d[y]){swap(x,y);}if(x==y){return ;}change2(1,1,n,s[x]+1,s[y]); } void rotate2(int x,int y) {if(son[x]){change1(1,1,n,s[x]+1);}if(son[y]){change1(1,1,n,s[y]+1);}while(top[x]!=top[y]){if(d[top[x]]<d[top[y]]){swap(x,y);}updata(1,1,n,s[top[x]],s[x]);change1(1,1,n,s[top[x]]);x=f[top[x]];change1(1,1,n,s[x]+1);}if(d[x]>d[y]){swap(x,y);}change1(1,1,n,s[x]);change1(1,1,n,s[x]+1);updata(1,1,n,s[x],s[y]); } int ask(int x,int y) {int res=0;int ans;while(top[x]!=top[y]){if(d[top[x]]<d[top[y]]){swap(x,y);}if(top[x]!=x){res+=query2(1,1,n,s[top[x]]+1,s[x]);}ans=query1(1,1,n,s[top[x]]);x=f[top[x]];res+=(ans^downdata(1,1,n,s[x]));}if(d[x]>d[y]){swap(x,y);}if(x==y){return res;}res+=query2(1,1,n,s[x]+1,s[y]);return res; } int main() {scanf("%d",&T);while(T--){num=0;tot=0;memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(f,0,sizeof(f));memset(d,0,sizeof(d));memset(s,0,sizeof(s));memset(to,0,sizeof(to));memset(son,0,sizeof(son));memset(top,0,sizeof(top));memset(sum,0,sizeof(sum));memset(size,0,sizeof(size));memset(head,0,sizeof(head));memset(next,0,sizeof(next));scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}dfs(1);dfs2(1,1);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d%d",&opt,&x,&y);if(opt==1){rotate1(x,y);}else if(opt==2){rotate2(x,y);}else{printf("%d\n",ask(x,y));}}} }

轉(zhuǎn)載于:https://www.cnblogs.com/Khada-Jhin/p/9719205.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ3862Little Devil I——树链剖分+线段树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。