洛谷P3690 【模板】Link Cut Tree （动态树）

Love The Way You Lie 2023-08-17 17:21 74阅读 0赞

# 【模板】Link Cut Tree （动态树） #

[题目传送门][Link 1]

## 解题思路 ##

妈妈我终于学会LCT了。

## 代码如下 ##

#include <bits/stdc++.h> using namespace std; const int N = 300005; int v[N], fa[N], ch[N][2], sum[N]; bool lazy[N]; inline bool get(int x) { return ch[fa[x]][1] == x; } inline void pushr(int x) { swap(ch[x][1], ch[x][0]); lazy[x] ^= 1; } inline void push_down(int x) { if(lazy[x]){ pushr(ch[x][0]); pushr(ch[x][1]); lazy[x] = 0; } } inline void update(int x) { sum[x] = sum[ch[x][0]] ^ sum[ch[x][1]] ^ v[x]; } inline bool isroot(int x) { return (!fa[x] || (ch[fa[x]][1] != x && ch[fa[x]][0] != x)); } inline void rotate(int x) { int y = fa[x], z = fa[y]; bool u = get(x), v = get(y); ch[y][u] = ch[x][u^1], fa[ch[x][u^1]] = y; if(!isroot(y)) ch[z][v] = x; fa[x] = z; ch[x][u^1] = y, fa[y] = x; update(y), update(x); } int sta[N]; inline void splay(int x) { int pos = 0; sta[++pos] = x; for(int i = x; !isroot(i); i = fa[i]) sta[++pos] = fa[i]; while(pos) push_down(sta[pos --]); while(!isroot(x)){ int y = fa[x]; if(!isroot(y)){ get(x) == get(y) ? rotate(y): rotate(x); } rotate(x); } } void access(int x) { for(int y = 0; x; y = x, x = fa[x]) splay(x), ch[x][1] = y, update(x); } void make_root(int x) { access(x);splay(x); pushr(x); } int find_root(int x) { access(x);splay(x); while(ch[x][0]){ push_down(x); x = ch[x][0]; } splay(x); return x; } void link(int x, int y) { make_root(x); if(find_root(y) != x) fa[x] = y; } void split(int x, int y) { make_root(x); access(y);splay(y); } void cut(int x, int y) { make_root(x); if(find_root(y) != x || fa[y] != x || ch[y][0]) return; fa[y] = ch[x][1] = 0; update(x); } int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++){ scanf("%d", &v[i]); sum[i] = v[i]; } for(int i = 1; i <= m; i ++){ int opt, x, y; scanf("%d%d%d", &opt, &x, &y); if(opt == 0){ split(x, y); printf("%d\n", sum[y]); } else if(opt == 1){ link(x, y); } else if(opt == 2){ cut(x, y); } else { splay(x); v[x] = y; update(x); } } return 0; }

转载于:https://www.cnblogs.com/whisperlzw/p/11404089.html

[Link 1]: https://www.luogu.org/problem/P3690