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之間有一條邊。

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

6

Data Constraint

對于40%的數據，N,Q≤1000

對于100%的數據，1≤N,Q≤100000

Solution

• 這題的思路很巧妙。考慮樹鏈剖分和并查集。

• 先把邊都連上，形成一些森林，處理樹鏈剖分的有關信息。

• 接著再逐個連邊，把深度高的點設為x，深度低的點設為y，y所在的鏈鏈頂為z。

• 再設x的子樹大小為m1，z的子樹大小為m2，有如下情況：

• ①：連邊操作，從y到z的子樹大小全部加上x的子樹大小（用線段樹區間加實現）

• ②：查詢操作，則答案即為m1*(m2-m1)。

Code

#include<cstdio> #include<algorithm> using namespace std; const int N=100001; struct data {bool z;int x,y; }a[N]; struct segment {int l,r,sum,c; }g[N<<2]; int tot,num; int first[N],next[N<<1],en[N<<1]; int fa[N],size[N],dep[N]; int top[N],son[N],tree[N],pre[N]; int f[N],t[N],h[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline void insert(int x,int y) {next[++tot]=first[x];first[x]=tot;en[tot]=y; } inline int get(int x) {if(f[x]==x) return x;return f[x]=get(f[x]); } inline void dfs1(int x) {dep[x]=dep[fa[x]]+1;size[x]=1;for(int i=first[x];i;i=next[i])if(en[i]!=fa[x]){fa[en[i]]=x;dfs1(en[i]);size[x]+=size[en[i]];if(!son[x] || size[son[x]]<size[en[i]]) son[x]=en[i];} } inline void dfs2(int x,int y) {top[pre[tree[x]=++num]=x]=y;if(!son[x]) return;dfs2(son[x],y);for(int i=first[x];i;i=next[i])if(en[i]!=fa[x] && en[i]!=son[x]) dfs2(en[i],en[i]); } inline void update(int v) {int ls=v<<1,rs=ls|1;if(g[v].c){g[ls].sum+=g[v].c;g[ls].c+=g[v].c;g[rs].sum+=g[v].c;g[rs].c+=g[v].c;g[v].c=0;} } inline void make(int v,int l,int r) {g[v].l=l,g[v].r=r;if(l==r){g[v].sum=1;return;}int mid=(l+r)>>1;make(v<<1,l,mid);make(v<<1|1,mid+1,r);g[v].sum=g[v<<1].sum+g[v<<1|1].sum+1; } inline void change(int v,int x,int y,int z) {if(g[v].l==x && g[v].r==y){g[v].sum+=z;g[v].c+=z;return;}update(v);int mid=(g[v].l+g[v].r)>>1;if(y<=mid) change(v<<1,x,y,z); elseif(x>mid) change(v<<1|1,x,y,z); else{change(v<<1,x,mid,z);change(v<<1|1,mid+1,y,z);} } inline int find(int v,int x) {if(g[v].l==g[v].r) return g[v].sum;update(v);int mid=(g[v].l+g[v].r)>>1;if(x<=mid) return find(v<<1,x);return find(v<<1|1,x); } int main() {int n=read(),q=read();for(int i=1;i<=q;i++){char ch=getchar();while(ch!='A' && ch!='Q') ch=getchar();a[i].x=read(),a[i].y=read();if(a[i].z=ch=='A'){insert(a[i].x,a[i].y);insert(a[i].y,a[i].x);}}for(int i=1;i<=n;i++)if(!size[i]){dfs1(i);dfs2(i,i);}make(1,1,n);for(int i=1;i<=n;i++) h[t[f[i]=i]=i]=1;for(int i=1;i<=q;i++){int x=a[i].x,y=a[i].y;if(dep[x]<dep[y]) swap(x,y);int f1=get(x),f2=get(y);if(a[i].z){int n1=y,n2=t[f2];int m1=top[n1],m2=top[n2];if(dep[m1]<dep[t[f2]]) m1=t[f2];if(dep[m2]<dep[t[f2]]) m2=t[f2];while(m1!=m2){if(dep[m1]<dep[m2]) swap(m1,m2),swap(n1,n2);change(1,tree[m1],tree[n1],h[f1]);n1=fa[m1],m1=top[n1];if(dep[m1]<dep[t[f2]]) m1=t[f2];}if(dep[n1]>dep[n2]) swap(n1,n2);change(1,tree[n1],tree[n2],h[f1]);h[f2]+=h[f1];if(dep[t[f1]]<dep[t[f2]]) t[f2]=t[f1];f[f1]=f2;}else{int m1=find(1,tree[x]),m2=find(1,tree[t[f2]])-m1;printf("%lld\n",(long long)m1*m2);}}return 0; }

方法二

• 顯然這道題也可以用可維護子樹信息的LCT。

• 那么 LCT 如何維護子樹信息呢？（以維護子樹大小為例）

• 我們可以多開一個數組記錄一個點虛樹上的大小信息，合并時直接并到該點上。

• 我們發現只有當 Access 或 Link 操作時會影響到信息記錄（其他操作都不會影響）。

• 當 Access 時，只需將虛樹信息加上原右兒子的 Size ，再減去新右兒子的 Size 即可。

• 而當 Link 時，相當于 xx 向 yy 添一條虛邊，

• 于是除了 makeroot(x) 外，再執行一遍 makeroot(y)，（消除修改 yy 對其子樹各節點信息的影響）

• 最后再將 yy 虛樹信息加上 xx 的 Size 即可。

• 時間復雜度 O(N log N)O(N log N) 。

Code2

#include<cstdio> #include<algorithm> #include<cctype> using namespace std; const int N=1e5+5; int top; int fa[N],size[N],s[N][2],g[N],st[N]; bool rev[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } inline bool pd(int x) {return x==s[fa[x]][1]; } inline bool isroot(int x) {return x^s[fa[x]][0] && x^s[fa[x]][1]; } inline void reverse(int x) {if(x) swap(s[x][0],s[x][1]),rev[x]^=1; } inline void update(int x) {size[x]=size[s[x][0]]+size[s[x][1]]+1+g[x]; } inline void down(int x) {if(rev[x]){reverse(s[x][0]),reverse(s[x][1]);rev[x]=false;} } inline void rotate(int x) {int y=fa[x],w=pd(x);if(s[y][w]=s[x][w^1]) fa[s[y][w]]=y;if((fa[x]=fa[y]) && !isroot(y)) s[fa[y]][pd(y)]=x;s[fa[y]=x][w^1]=y;update(y); } inline void splay(int x) {for(int y=st[top=1]=x;!isroot(y);y=fa[y]) st[++top]=fa[y];while(top) down(st[top--]);for(int y;!isroot(x);rotate(x))if(!isroot(y=fa[x])) rotate(pd(x)==pd(y)?y:x);update(x); } inline void access(int x) {for(int y=0;x;x=fa[y=x]){splay(x);g[x]+=size[s[x][1]];g[x]-=size[s[x][1]=y];update(x);} } inline void mkroot(int x) {access(x),splay(x),reverse(x); } inline void link(int x,int y) {mkroot(x),mkroot(y);g[fa[x]=y]+=size[x];update(y); } int main() {int n=read(),m=read();for(int i=1;i<=n;i++) size[i]=1;while(m--){char ch=getchar();int x=read(),y=read();if(ch=='A') link(x,y); else{mkroot(x),access(y),splay(y);printf("%lld\n",(long long)size[x]*(size[y]-size[x]));}}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3766. 【BJOI2014】大融合的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。