正題

luogu 4219

---

題目大意

給你一棵樹（初始都無連邊），讓你進行以下操作：

1.連接兩個點

2.查詢一條邊被多少條路徑經過

---

解題思路

因為有邊的修改，可以用LCT來維護這棵樹

一條邊的經過次數，就相當于連接的兩棵子樹的大小之積

那么維護子樹大小即可

---

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define N 100010 using namespace std; int n, q, x, y; char c; struct LCT {#define ls son[x][0]#define rs son[x][1]int p[N], siz[N], size[N], fa[N], son[N][2];bool NR(int x){return fa[x] && (son[fa[x]][0] == x || son[fa[x]][1] == x);}bool IRS(int x){return son[fa[x]][1] == x;}void push_up(int x){size[x] = size[ls] + size[rs] + siz[x];return;}void pushr(int x){p[x] ^= 1;swap(ls, rs);return;}void push_down(int x){if (p[x]){p[x] = 0;if (ls) pushr(ls);if (rs) pushr(rs);}return;}void rotate(int x){int y = fa[x], z = fa[y], k = IRS(x), g = son[x][!k];if (NR(y)) son[z][IRS(y)] = x;if (g) fa[g] = y;fa[y] = x;fa[x] = z;son[x][!k] = y;son[y][k] = g;push_up(y);return;}void push_hall(int x){if (NR(x)) push_hall(fa[x]);push_down(x);return;}void Splay(int x){push_hall(x);while(NR(x)){if (NR(fa[x])){if (IRS(x) == IRS(fa[x])) rotate(fa[x]);else rotate(x);}rotate(x);}push_up(x);return;}void access(int x){for (int y = 0; x; x = fa[y = x]){Splay(x);siz[x] += size[rs] - size[y];rs = y;push_up(x);}return;}void make_root(int x){access(x);Splay(x);pushr(x);return;}void Split(int x, int y){make_root(x);access(y);Splay(y);return;}void link(int x, int y){make_root(x);make_root(y);fa[x] = y;siz[y] += size[x];push_up(y);return;} }T; int main() {scanf("%d%d", &n, &q);for (int i = 1; i <= n; ++i)T.size[i] = T.siz[i] = 1;while(q--){scanf("%s%d%d", &c, &x, &y);if (c == 'A') T.link(x, y);else{T.Split(x, y);printf("%lld\n", 1ll * T.siz[x] * T.siz[y]);}}return 0; }

總結

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

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