hdu4897（樹鍊剖分）

啟迪：果然，離成功就差一步，如果剛剛我放棄了，停下debug的步伐，那我終不會知道成功原來并不遙遠，就在霎那間，在我執着的信念前它終會出現

題目：樹鍊剖分，細節真多，思路有一些亂，不過隻要把所有情況考慮上了就ok了

注意事項在代碼中

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#define debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
inline int read()
{
	int ans,f=1;char ch;
	while ((ch=getchar())<'0'||ch>'9') if (ch=='-') f=-1;ans=ch-'0';
	while ((ch=getchar())>='0'&&ch<='9') ans=ans*10+ch-'0';
	return ans*f;
}
const int N=300090;
int to[N*2],pre[N*2],head[N*2],btot;//注意雙向邊數組開兩倍
void addedge(int x,int y) {to[++btot]=y;pre[btot]=head[x];head[x]=btot;}// add edge
int dep[N],fa[N],top[N],size[N],son[N],id[N],tot;//tree devide
struct aa
{
	int l,r,sum,rev;
	int kk;//判斷這個區間有沒有被翻轉
}a[N*4];//線段樹開4倍
void init()//清空
{
	memset(head,0,sizeof(head));btot=0;
	memset(fa,0,sizeof(fa));
	memset(top,0,sizeof(top));
	memset(size,0,sizeof(size));
	memset(son,0,sizeof(son));
	memset(id,0,sizeof(id));tot=0;
	memset(dep,0,sizeof(dep));
	memset(a,0,sizeof(a));
}

int n,m;
void dfs1(int u,int depth,int f)
{
	fa[u]=f;dep[u]=depth;size[u]=1;
	int max_size=0;son[u]=0;
	for (int i=head[u];i;i=pre[i])
	if (to[i]!=f)
	{
		dfs1(to[i],depth+1,u);
		size[u]+=size[to[i]];
		if (size[to[i]]>max_size) max_size=size[to[i]],son[u]=to[i];
	}
}
void dfs2(int u,int anc)
{
	top[u]=anc;id[u]=++tot;
	if (son[u]) dfs2(son[u],anc);
	for (int i=head[u];i;i=pre[i])
	if (to[i]!=fa[u]&&to[i]!=son[u]) dfs2(to[i],to[i]);
}//樹鍊剖分
void build(int i,int l,int r)
{
	a[i].l=l;a[i].r=r;
	if (l==r) return;
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
}//建立線段樹，把所有節點建立
void up(int i) 
{
	a[i].sum=0;
	if (a[i<<1].l) a[i].sum+=a[i<<1].sum;
	if (a[i<<1|1].l) a[i].sum+=a[i<<1|1].sum;//注意要保證有這個孩子再加，啟下
}
void down(int i)
{
	if (a[i].rev)
	{
		a[i].rev=0;a[i<<1].rev^=1;a[i<<1|1].rev^=1;
		a[i<<1].sum=(a[i<<1].r-a[i<<1].l+1)-a[i<<1].sum;//因為，當i為子節點時，這個地方可能導緻空節點num不為0，承上
		a[i<<1|1].sum=(a[i<<1|1].r-a[i<<1|1].l+1)-a[i<<1|1].sum;
	}
}
void rever(int i,int l,int r)//線段樹中旋轉區間
{
	down(i);
	if (a[i].l==l&&a[i].r==r) 
	{
		a[i].rev^=1;
		a[i].sum=(a[i].r-a[i].l+1)-a[i].sum;
		return;
	}
	int mid=(a[i].l+a[i].r)>>1;
	if (mid>=r) rever(i<<1,l,r);
	else if (mid<l) rever(i<<1|1,l,r);
	else rever(i<<1,l,mid),rever(i<<1|1,mid+1,r);
	up(i);
}
void rever(int x,int y)//樹上旋轉x~y的路徑，——詢問1
{
	while (top[x]!=top[y])
	{
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		rever(1,id[top[x]],id[x]);
		x=fa[top[x]];
	}
	if (dep[x]>dep[y]) swap(x,y);
	if (x!=y) rever(1,id[x]+1,id[y]);//因為一個點代表它到father的這條邊
}
void bj(int i,int l,int r)
{
	if (a[i].l==l&&a[i].r==r) 
	{
		a[i].kk^=1;
		return;
	}
	int mid=(a[i].l+a[i].r)>>1;
	if (mid>=r) bj(i<<1,l,r);
	else if (mid<l) bj(i<<1|1,l,r);
	else bj(i<<1,l,mid),bj(i<<1|1,mid+1,r);
}
int pan(int i,int x)
{
	int ans=a[i].kk;
	if (a[i].l==a[i].r) return ans;
	int mid=(a[i].l+a[i].r)>>1;
	if (mid>=x)  return ans^pan(i<<1,x);else return ans^pan(i<<1|1,x);//一個點它是否被反轉，就是從線段樹根節點到這個子節點有多少包括他的區間被整體反轉這樣統計是否反轉時，隻需用從根查到子節點就好
}
int find(int i,int l,int r)
{
	down(i);
	if (a[i].l==l&&a[i].r==r) return a[i].sum;
	int mid=(a[i].l+a[i].r)>>1;
	if (mid>=r) return find(i<<1,l,r);
	if (mid<l) return find(i<<1|1,l,r);
	return find(i<<1,l,mid)+find(i<<1|1,mid+1,r);
}
void query(int x,int y)//x~y的黑邊數量——詢問3
{
	int ans=0;
	while (top[x]!=top[y])
	{
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		if (x!=top[x]) ans+=find(1,id[top[x]]+1,id[x]);//處理重邊的黑邊number
		ans+=(pan(1,id[fa[top[x]]])^find(1,id[top[x]],id[top[x]]));//pan判斷父親的标記，find邊本身的标記，取異或，是否被變為黑色
		x=fa[top[x]];//上面一定要是id【fa。。】我們把樹資訊移到線段樹中了，操作都應該線上段樹中修改
	}
	if (dep[x]>dep[y]) swap(x,y);
	if (x!=y) ans+=find(1,id[x]+1,id[y]);
	printf("%d\n",ans);
}
void near_rever(int x,int y)//路徑鄰邊更改——詢問2。。。。。實際上就是把一些邊直接反轉，一些邊标記反轉
{
	while (top[x]!=top[y])
	{
		if (dep[top[x]]<dep[top[y]]) swap(x,y);
		bj(1,id[top[x]],id[x]);//标記這些節點的所有輕兒子的邊都被反轉
		if (son[x]) rever(1,id[son[x]],id[son[x]]);//如果有重兒子直接反轉
		rever(1,id[top[x]],id[top[x]]);//把最上面的輕邊反轉，和下一次循環時标記反轉最底下的邊抵消
		x=fa[top[x]];
	}
	if (dep[x]>dep[y])swap(x,y);
	bj(1,id[x],id[y]);
	rever(1,id[x],id[x]);//把最上面的邊反轉
	if (son[y]) rever(1,id[son[y]],id[son[y]]);
}
int main()
{
	int T=read();
	while (T--)
	{
		init();
		n=read();
		int x,y;
		for (int i=1;i<n;i++) 
		{
			x=read();y=read();
			addedge(x,y);addedge(y,x);
		}//add edge
		dfs1(1,1,0);
		dfs2(1,1);
		build(1,1,tot);
		int q=read(),t;
		while (q--)
		{
			t=read(),x=read(),y=read();
			switch(t)
			{
				case 1:rever(x,y);break;
				case 2:near_rever(x,y);break;
				case 3:query(x,y);break;//after switch,we must break!!! 
			}
		}
	}
	return 0;
}