【题意】给定n个点的树，从无到有加边，过程中动态询问当前图某条边两端连通点数的乘积，n<=10^5。
【算法】线段树合并+并查集 （||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#include #include #include using namespace std;const int maxn=200010;int n,m,first[maxn],root[maxn],q[maxn][5],d[maxn],g[maxn],tot,cnt,dfsnum,fa[maxn];char s[10];struct edge{ int v,from;}e[maxn*2];struct tree{ int l,r,sum;}t[maxn*40];int read(){ char c;int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0';}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)>>1; if(y<=mid)insert(l,mid,t[x].l,y); else insert(mid+1,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)>>1,sum=0; if(left<=mid)sum=ask(l,mid,t[k].l,left,right); if(right>mid)sum+=ask(mid+1,r,t[k].r,left,right); return sum;} int main(){ n=read();m=read(); for(int i=1;i<=m;i++){ scanf("%s",s); if(s[0]=='A'){ q[i][0]=0;q[i][1]=read();q[i][2]=read(); ins(q[i][1],q[i][2]);ins(q[i][2],q[i][1]); } else{ q[i][0]=1;q[i][1]=read();q[i][2]=read(); } } for(int i=1;i<=n;i++)if(!d[i])dfs(i,0); for(int i=1;i<=n;i++)insert(1,n,root[i],d[i]); for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=m;i++){ if(d[q[i][1]]>d[q[i][2]])swap(q[i][1],q[i][2]);//1fa 2son if(!q[i][0]){ root[find(q[i][1])]=merge(root[find(q[i][1])],root[find(q[i][2])]); fa[fa[q[i][2]]]=fa[q[i][1]];//zhi xiang } else{ int sonsize=ask(1,n,root[find(q[i][2])],d[q[i][2]],g[q[i][2]]); int fasize=t[root[find(q[i][1])]].sum; printf("%d\n",sonsize*(fasize-sonsize)); } } return 0;}