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

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

#includeusing 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#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 secondinline 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 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 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 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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。