题解：P14411 [JOISC 2015] 道路建设 / Road Development

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mp(i,j) make_pair(i,j)
const int N=3e5+10;
int n,Q;
struct node{
	int op,x,y,val;
}q[N];
int ans[N],F[N];
int findx(int x){
	if(x!=F[x])F[x]=findx(F[x]);
	return F[x];
}
vector<int> g[N];
int dfn[N],num=0,son[N],siz[N],dep[N],top[N],f[N];
inline void dfs(int u,int fa){
	son[u]=0;siz[u]=1;
	dep[u]=dep[fa]+1;f[u]=fa;
	for(int v:g[u]){
		if(v==fa)continue;
		dfs(v,u);
		siz[u]+=siz[v];
		if(!son[u]||siz[son[u]]<siz[v])son[u]=v;
	}
}
inline void dfs2(int x,int topx){
	top[x]=topx;
	dfn[x]=++num;
	if(!son[x])return;
	dfs2(son[x],topx);
	for(int y:g[x]){
		if(y!=son[x]&&y!=f[x])dfs2(y,y);
	}
	return;
}
struct BIT{
	int t[N<<2],tag[N<<2];
	inline void push_up(int x){
		t[x]=t[x*2]+t[x*2+1];
		return;
	}
	inline void push_down(int l,int r,int x){
		if(tag[x]!=-1){
			int mid=l+r>>1,k=tag[x];
			tag[x*2]=k;tag[x*2+1]=k;
			t[x*2]=(mid-l+1)*k;t[x*2+1]=(r-mid)*k;
			tag[x]=-1;
		}
		return;
	}
	inline void build(int l,int r,int x){
		tag[x]=-1;t[x]=0;
		if(l==r)return;
		int mid=l+r>>1;
		build(l,mid,x*2);
		build(mid+1,r,x*2+1);
		return;
	}
	inline void update(int L,int R,int l,int r,int x,int k){
		if(L<=l&&r<=R){
			t[x]=(r-l+1)*k;
			tag[x]=k;
			return;
		}
		push_down(l,r,x);
		int mid=l+r>>1;
		if(L<=mid)update(L,R,l,mid,x*2,k);
		if(R>mid)update(L,R,mid+1,r,x*2+1,k);
		push_up(x);
		return;
	}
	inline int ask(int L,int R,int l,int r,int x){
		if(L<=l&&r<=R)return t[x];
		push_down(l,r,x);
		int mid=l+r>>1,res=0;
		if(L<=mid)res+=ask(L,R,l,mid,x*2);
		if(R>mid)res+=ask(L,R,mid+1,r,x*2+1);
		return res;
	}
}tree;
inline void update_range(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		tree.update(max(1ll,dfn[top[x]]-1),dfn[x]-1,1,n,1,k);
		x=f[top[x]];
	}
	if(x==y)return;
	else{
		if(dep[x]>dep[y])swap(x,y);
		tree.update(dfn[x],dfn[y]-1,1,n,1,k);
	}
	return;
}
inline int ask_range(int x,int y){
	int res=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		res+=tree.ask(max(1ll,dfn[top[x]]-1),dfn[x]-1,1,n,1);
		//cout<<"x="<<x<<" top["<<x<<"]="<<top[x]<<" dfn[top[x]]-1="<<dfn[top[x]]-1<<" dfn[x]-1="<<dfn[x]-1<<"\n";
		x=f[top[x]];
	}
	if(x==y)return res;
	if(dep[x]>dep[y])swap(x,y);
	res+=tree.ask(dfn[x],dfn[y]-1,1,n,1);
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>Q;
	for(int i=1;i<=n;i++)F[i]=i;
	for(int i=1;i<=Q;i++){
		cin>>q[i].op>>q[i].x>>q[i].y;
		int fu=findx(q[i].x),fv=findx(q[i].y);
		//cout<<"i="<<i<<" fu="<<fu<<" fv="<<fv<<"\n";
		if(q[i].op==1){
			if(fu==fv)q[i].val=0;//本身就联通不需要加边 
			else{
				F[fu]=fv;q[i].val=1;//不联通，加边然后改成1，查询时查询有多少个1即可 
				g[q[i].x].push_back(q[i].y);
				g[q[i].y].push_back(q[i].x);
				//cout<<"u="<<q[i].x<<" v="<<q[i].y<<"\n";
			}
		}
		else if(fu!=fv&&q[i].op==2)ans[i]=-1;
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i,0);
			dfs2(i,i);
		} 
	}
	//for(int i=1;i<=n;i++)cout<<"dfn["<<i<<"]="<<dfn[i]<<" ";cout<<"\n";
	for(int i=1;i<=Q;i++){
		if(q[i].op==1){
			update_range(q[i].x,q[i].y,q[i].val);
			//cout<<"i="<<i<<" val="<<q[i].val<<"\n";
		}
		else{
			if(ans[i]==-1)continue;
			else ans[i]=ask_range(q[i].x,q[i].y);
		}
	}
	for(int i=1;i<=Q;i++)if(q[i].op==2)cout<<ans[i]<<"\n";
	return 0;
}
/*3 7
1 1 2
2 2 1
2 2 3
1 2 1
2 1 2
1 2 3
2 1 3*/