【洛谷P4219】【BJOI2014】—大融合（线段树合并）

传送门

线段树合并基础题

考虑到我们先把最后连完所有边的森林建出来

发现这样每次连边的操作就是在合并两个子树

然后又发现对于一条边$(u,v)epsilon subtree_{rt}$

经过这条边的路径数就是$siz[rt]*(siz[rt]-siz[v])$

那么维护一下$size$就可以了

调了半天发现自己$siz$数组开小了

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	int res=0,f=1;
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
	return res*f;
}
const int N=100005;
int in[N],out[N],rt[N],siz[N<<5],n,q,adj[N],nxt[N<<1],to[N<<1],tot,dfn,cnt,lc[N<<5],rc[N<<5],dep[N],fa[N];
char c[5];
struct ask{
	int u,v,op;
}a[N];
inline void addedge(int u,int v){
	nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
int find(int x){
	return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
#define mid ((l+r)>>1)
void update(int &u,int l,int r,int k){
	if(!u)u=++tot;siz[u]=1;
	if(l==r)return;
	if(k<=mid)update(lc[u],l,mid,k);
	else update(rc[u],mid+1,r,k);
}
void merge(int &u,int v,int l,int r){
	if(!u||!v){u+=v;return;}
	siz[u]+=siz[v];
	if(l==r)return;
	merge(lc[u],lc[v],l,mid);
	merge(rc[u],rc[v],mid+1,r);
}
int query(int u,int l,int r,int st,int des){
	if(st<=l&&r<=des)return siz[u];
	int res=0;
	if(st<=mid)res+=query(lc[u],l,mid,st,des);
	if(mid<des)res+=query(rc[u],mid+1,r,st,des);
	return res;
}
void dfs(int u,int fa){
	in[u]=++dfn;
	for(int e=adj[u];e;e=nxt[e]){
		int v=to[e];
		if(v==fa)continue;
		dep[v]=dep[u]+1;
		dfs(v,u);
	}
	out[u]=dfn;
}
int main(){
	n=read(),q=read();
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=q;i++){
		scanf("%s",c);
		int u=read(),v=read(),k=(c[0]!='A');
		a[i]=(ask){u,v,k};if(!k)addedge(v,u),addedge(u,v);
	}
	for(int i=1;i<=n;i++){
		if(!in[i])dfs(i,0);
		update(rt[i],1,n,in[i]);
	}
	for(int i=1;i<=q;i++){
		int u=a[i].u,v=a[i].v;
		if(dep[u]>dep[v])swap(u,v);
		if(!a[i].op){
			int f1=find(u),f2=find(v);
			fa[f2]=f1,merge(rt[f1],rt[f2],1,n);
		}
		else{
			int x=find(u),y=query(rt[x],1,n,in[v],out[v]);
			cout<<(y*(siz[rt[x]]-y))<<'
';
		}
	}
}