2025年H、智乃的树旋转(hard version)

科技前沿 • 2025-01-07 12:18 • 阅读 51

大家好，我是讯享网，很高兴认识大家。

#include<bits/stdc++.h> using namespace std; #define rep(i,l,r) for(int i=(l);i<=(r);i++) #define per(i,l,r) for(int i=(l);i>=(r);i--) #define ll long long #define pii pair<int, int> #define mset(s,t) memset(s,t,sizeof(t)) #define mcpy(s,t) memcpy(s,t,sizeof(t)) #define fir first #define pb push_back #define sec second inline int read () { int x = 0, f = 0; char ch = getchar(); while (!isdigit(ch)) f |= ch=='-',ch= getchar(); while (!isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return f?-x:x; } template<typename T> void print(T x) { if (x < 0) putchar('-'), x = -x; if (x >= 10) print(x/10); putchar(x % 10 + '0'); } const int N = 1e5 + 10; struct tree { int fa; int ch[2]; }t[N], a[N]; int n; vector<int> ans; bool vis[N] = {1}; void rot (int root) { int fa = t[root].fa; int gfa = t[fa].fa; int t1 = (root != t[fa].ch[0]); int t2 = (fa != t[gfa].ch[0]); int ch = t[root].ch[1^t1]; t[root].fa = gfa; t[root].ch[1^t1] = fa; //折一下 t[fa].ch[0^t1] = ch; //不折 t[fa].fa = root; t[ch].fa = fa; t[gfa].ch[0^t2] = root; //不折 return; } void splay (int root) { while (!vis[t[root].fa]) { ans.pb(root); rot(root); } } void dfs (int u) { splay(u); vis[u] = 1; if (a[u].ch[0]) dfs(a[u].ch[0]); if (a[u].ch[1]) dfs(a[u].ch[1]); } int input_tree(tree* t, int n) { int x, y; std::vector<bool> v(n + 1, true); for (int i = 1; i <= n; ++i) { scanf("%d %d", &x, &y); v[x] = v[y] = false; t[i].ch[0] = x; t[i].ch[1] = y; if (x)t[x].fa = i; if (y)t[y].fa = i; } for (int i = 1; i <= n; ++i) { if (v[i])return i; } return -1; } void solve() { cin >> n; int root_a = input_tree(a, n); int root_t = input_tree(t, n); dfs(root_a); cout << ans.size() << endl; for (auto t : ans) cout << t << endl; } int main () { solve(); return 0; }

讯享网

对于一个点一直转，最终会转到根节点思考技巧:左边有一个，右边不知道，对于不知道的情况也给予描述。小问题思考 splay

2025年H、智乃的树旋转(hard version)

相关推荐