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;

}

秒客网