LOJ#2230. 「BJOI2014」大融合

題目描述

小強要在$N$個孤立的星球上建立起一套通信系統。這套通信系統就是連接$N$個點的一個樹。這個樹的邊是一條一條添加上去的。

在某個時刻，一條邊的負載就是它所在的當前能夠聯通的樹上路過它的簡單路徑的數量。

例如，在上圖中，現在一共有五條邊。其中，$(3,8)$這條邊的負載是$6$，因為有六條簡單路徑$2-3-8,\ 2-3-8-7,\ 3-8,\ 3-8-7,\ 4-3-8,\ 4-3-8-7$路過了$(3,8)$。

現在，你的任務就是隨著邊的添加，動態的回答小強對于某些邊的負載的詢問。

輸入格式

第一行包含兩個整數$N,Q$，表示星球的數量和操作的數量。星球從$1$開始編號。

接下來的$Q$行，每行是如下兩種格式之一：

A x y?表示在$x$和$y$之間連一條邊。保證之前$x$和$y$是不聯通的。
Q x y?表示詢問$(x,y)$這條邊上的負載。保證$x$和$y$之間有一條邊。

輸出格式

對每個查詢操作，輸出被查詢的邊的負載。

樣例

樣例輸入

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

樣例輸出

6

數據范圍與提示

對于所有數據，$1 \leq N,Q \leq 100000$。

---

題解Here!

?

$LCT$大法好！

維護虛樹中每個節點的虛子節點個數。

連邊時注意：不是$makeroot$，是$split$。（坑了我好久。。。）

還有$access$時維護一下即可。

最后答案就是：

$$\text{x的虛子節點個數}\times(\text{y的虛子節點個數}-\text{x的虛子節點個數})$$

附代碼：

#include<iostream> #include<algorithm> #include<cstdio> #define MAXN 100010 using namespace std; int n,m; struct node{int f,v,s,flag,son[2]; }a[MAXN]; inline int read(){int date=0,w=1;char c=0;while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}return date*w; } inline bool isroot(int rt){return a[a[rt].f].son[0]!=rt&&a[a[rt].f].son[1]!=rt; } inline void pushup(int rt){if(!rt)return;a[rt].s=a[a[rt].son[0]].s+a[a[rt].son[1]].s+a[rt].v+1; } inline void pushdown(int rt){if(!rt||!a[rt].flag)return;a[a[rt].son[0]].flag^=1;a[a[rt].son[1]].flag^=1;a[rt].flag^=1;swap(a[rt].son[0],a[rt].son[1]); } inline void turn(int rt){int x=a[rt].f,y=a[x].f,k=a[x].son[0]==rt?1:0;if(!isroot(x)){if(a[y].son[0]==x)a[y].son[0]=rt;else a[y].son[1]=rt;}a[rt].f=y;a[x].f=rt;a[a[rt].son[k]].f=x;a[x].son[k^1]=a[rt].son[k];a[rt].son[k]=x;pushup(x);pushup(rt); } void splay(int rt){int top=0,stack[MAXN];stack[++top]=rt;for(int i=rt;!isroot(i);i=a[i].f)stack[++top]=a[i].f;while(top)pushdown(stack[top--]);while(!isroot(rt)){int x=a[rt].f,y=a[x].f;if(!isroot(x)){if((a[y].son[0]==x)^(a[x].son[0]==rt))turn(rt);else turn(x);}turn(rt);} } void access(int rt){for(int i=0;rt;i=rt,rt=a[rt].f){splay(rt);a[rt].v+=a[a[rt].son[1]].s-a[i].s;a[rt].son[1]=i;pushup(rt);} } inline void makeroot(int rt){access(rt);splay(rt);a[rt].flag^=1;} inline void split(int x,int y){makeroot(x);access(y);splay(y);} inline void link(int x,int y){split(x,y);a[x].f=y;a[y].v+=a[x].s;pushup(y); } void work(){char ch[2];int x,y;n=read();m=read();for(int i=1;i<=n;i++)a[i].s=1;while(m--){scanf("%s",ch);x=read();y=read();if(ch[0]=='A')link(x,y);if(ch[0]=='Q'){split(x,y);printf("%lld\n",(long long)a[x].s*(a[y].s-a[x].s));}} } int main(){work(); return 0; }

?

轉載于:https://www.cnblogs.com/Yangrui-Blog/p/9940964.html

總結

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

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