【题意】给定n个点的树,从无到有加边,过程中动态询问当前图某条边两端连通点数的乘积,n<=10^5。
【算法】线段树合并+并查集 (||LCT(LCT维护子树信息 LCT维护子树信息(+启发式合并))——嗷嗷待补)
【题解】先将所有边离线加入计算dfs序(套路,强制固定原树形态)
对于一条边(u,v),fa[v]=u,ans=size[v]*(sz-size[v]),size[v]是v子树大小,sz是u-v所在连通块的大小(该边在查询前一定已经加入)
对每个点维护一棵dfs序线段树表示哪些点在此连通块,初始状态对自己的dfs序+1,那么询问子树size就是区间求和(子树是dfs序上的一段区间)。
用并查集维护连通块,强制连通块的根是深度最小的点的线段树,加边就是线段树合并了。
(当所有单链不一致的时候,merge不用做叶子结点处理。)
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
const int maxn=;
int n,m,first[maxn],root[maxn],q[maxn][],d[maxn],g[maxn],tot,cnt,dfsnum,fa[maxn];
char s[];
struct edge{int v,from;}e[maxn*];
struct tree{int l,r,sum;}t[maxn*];
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
void ins(int u,int v){tot++;e[tot].v=v;e[tot].from=first[u];first[u]=tot;}
void dfs(int x,int fa){
d[x]=++dfsnum;
for(int i=first[x];i;i=e[i].from)if(e[i].v!=fa){
dfs(e[i].v,x);
}
g[x]=dfsnum;
}
void insert(int l,int r,int &x,int y){
if(!x)x=++cnt;t[x].sum++;
if(l==r)return;
int mid=(l+r)>>;
if(y<=mid)insert(l,mid,t[x].l,y);
else insert(mid+,r,t[x].r,y);
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int merge(int x,int y){
if(!x||!y)return x^y;
t[x].l=merge(t[x].l,t[y].l);
t[x].r=merge(t[x].r,t[y].r);
t[x].sum=t[t[x].l].sum+t[t[x].r].sum;
return x;
}
int ask(int l,int r,int k,int left,int right){
if(left<=l&&r<=right)return t[k].sum;
int mid=(l+r)>>,sum=;
if(left<=mid)sum=ask(l,mid,t[k].l,left,right);
if(right>mid)sum+=ask(mid+,r,t[k].r,left,right);
return sum;
}
int main(){
n=read();m=read();
for(int i=;i<=m;i++){
scanf("%s",s);
if(s[]=='A'){
q[i][]=;q[i][]=read();q[i][]=read();
ins(q[i][],q[i][]);ins(q[i][],q[i][]);
}
else{
q[i][]=;q[i][]=read();q[i][]=read();
}
}
for(int i=;i<=n;i++)if(!d[i])dfs(i,);
for(int i=;i<=n;i++)insert(,n,root[i],d[i]);
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=m;i++){
if(d[q[i][]]>d[q[i][]])swap(q[i][],q[i][]);//1fa 2son
if(!q[i][]){
root[find(q[i][])]=merge(root[find(q[i][])],root[find(q[i][])]);
fa[fa[q[i][]]]=fa[q[i][]];//zhi xiang
}
else{
int sonsize=ask(,n,root[find(q[i][])],d[q[i][]],g[q[i][]]);
int fasize=t[root[find(q[i][])]].sum;
printf("%d\n",sonsize*(fasize-sonsize));
}
}
return ;
}