BZOJ4530: [Bjoi2014]大融合

Description

小强要在N个孤立的星球上建立起一套通信系统。这套通信系统就是连接N个点的一个树。这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够联通的树上路过它的简单路径的数量。例如，在上图中，现在一共有了5条边。其中，(3,8)这条边的负载是6，因为有六条简单路径2-3-8,2-3-8-7,3-8,3-8-7,4-3-8,4-3-8-7路过了(3,8)。现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

Input

第一行包含两个整数N,Q，表示星球的数量和操作的数量。星球从1开始编号。接下来的Q行，每行是如下两种格式之一：A x y 表示在x和y之间连一条边。保证之前x和y是不联通的。Q x y 表示询问(x,y)这条边上的负载。保证x和y之间有一条边。1≤N,Q≤100000

Output

对每个查询操作，输出被查询的边的负载。

Sample Input

8 6
A 2 3
A 3 4
A 3 8
A 8 7
A 6 5
Q 3 8

Sample Output

HINT

Source

鸣谢佚名上传

数据结构简单题嘛，我们发现答案为min(siz[x],siz[y])*(SIZE[x]-min(siz[x],siz[y]))，其中siz[x]表示以x为根子树的大小，SIZE[x]表示x所在树的大小。添加一条边x-y时启发式合并一下，设x为SIZE较小的那一个，将x所在的树暴力重构，用动态树将y到其根的路径上所有siz值加上SIZE[x]。时间复杂度仍为O(MlogN)。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define lc ch[x][0]
#define rc ch[x][1]
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,1,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
    int x=0,f=1;char c=Getchar();
    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
const int maxn=100010;
int n,m,pa[maxn],siz[maxn],ch[maxn][2],s[maxn],add[maxn],pre[maxn],fa[maxn];
int findset(int x) {return x==pa[x]?x:pa[x]=findset(pa[x]);}
void Add(int x,int v) {if(x) add[x]+=v,s[x]+=v;}
void pushdown(int x) {
if(add[x]) Add(lc,add[x]),Add(rc,add[x]),add[x]=0;
}
void rotate(int x) {
int y=pre[x],z=pre[y],d=ch[y][0]==x;
ch[y][d^1]=ch[x][d];pre[ch[x][d]]=y;
ch[z][ch[z][1]==y]=x;pre[x]=z;
ch[x][d]=y;pre[y]=x;
}
int ST[maxn],top;
void splay(int x) {
for(int i=x;i;i=pre[i]) ST[++top]=i;
if(top!=1) fa[x]=fa[ST[top]],fa[ST[top]]=0;
while(top) pushdown(ST[top--]);
while(pre[x]) rotate(x);
}
void access(int x) {
for(int y=0;x;x=fa[x]) {
splay(x);pre[ch[x][1]]=0;fa[ch[x][1]]=x;
ch[x][1]=y;pre[y]=x;y=x;
}
}
int first[maxn],next[maxn<<1],to[maxn<<1],e;
void AddEdge(int u,int v) {
to[++e]=v;next[e]=first[u];first[u]=e;
to[++e]=u;next[e]=first[v];first[v]=e;
}
void dfs(int x,int f) {
fa[x]=f;lc=rc=0;pre[x]=0;s[x]=1;
ren if(to[i]!=f) dfs(to[i],x),s[x]+=s[to[i]];
}
void link(int x,int y) {
AddEdge(x,y);
int f1=findset(x),f2=findset(y);
if(siz[f1]>siz[f2]) swap(f1,f2),swap(x,y);
pa[f1]=f2;siz[f2]+=siz[f1];
access(y);splay(y);Add(y,siz[f1]);
dfs(x,y);
}
int query(int x) {splay(x);return s[x];}
int main() {
n=read();m=read();
rep(i,1,n) siz[i]=s[i]=1,pa[i]=i;
rep(i,1,m) {
char c=Getchar();
while(!isalpha(c)) c=Getchar();
if(c=='A') link(read(),read());
else {
int x=read(),y=read();
int sum=min(query(y),query(x));
printf("%lld\n",(ll)sum*(siz[findset(x)]-sum));
}
}
return 0;
}