题解 | #智乃的树旋转(hard version)#

智乃的树旋转(hard version)

https://ac.nowcoder.com/acm/contest/23478/H

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

还是注意这么一句话智乃最近学习了树旋转，树旋转的本质是二叉树旋转轴节点与其父节点父子关系的改变

思考这么一个问题：如果对某一个非根节点，一直作为旋转轴进行旋转，那么最后会发生什么。

显然，最终该节点一定被转到了整棵树的根部。

当你意识到这个问题之后，此时你仿佛tarjan灵魂附体，你发明了splay伸展树（当然，如果只是简单的一直旋转，这种操作称之为单旋，对于平衡树而言复杂度是假的）。

不过抛开时间复杂度不谈，splay的核心思想就是如果对二叉树的某个节点一直进行旋转，则该节点最终会被放到根的位置，而树结构修改根节点信息是 $O (1)$ 的。至于为什么最终splay的旋转是复杂的双层旋转，是由于双旋的均摊复杂度是 $O (l o g N)$ 。

不过本题你写单旋写双旋都可以通过，甚至对于本题而言,写单旋更优。

对于本题而言，构造双层旋转的次数上界为 $N^{2}$ 次，构造单层旋转的次数上界为 $\frac{N\cdot (N-1)}{2}$ 。（我并没有卡双旋，因为这样会很毒瘤）

void dfs(int root)
{
    splay(root);
    vis[root] = true;
    if (a[root].ch[0])dfs(a[root].ch[0]);
    if (a[root].ch[1])dfs(a[root].ch[1]);
}

核心代码就是一个先序遍历，当遍历到需要还原的节点时就伸展到根，然后从打乱的树中删除，删除可以直接打懒标记。

时间复杂度 $O (N^{2})$ ，空间复杂度 $O (1)$ 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
struct tree
{
    int fa;
    int ch[2];
} t[MAXN], a[MAXN];
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;
}
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;
}
vector<int>ans;
bool vis[MAXN] = {true};
int n, root_a, root_t;
//单层旋转
void splay(int root)
{
    while (!vis[t[root].fa])
    {
        ans.push_back(root);
        rot(root);
    }
    return;
}
/*
//双层旋转
void splay(int root)
{
    while(!vis[t[root].fa])
    {
        int fa=t[root].fa,gfa=t[fa].fa;
        if(gfa&&!vis[gfa])
        {
            if((t[fa].ch[0]==root)^(t[gfa].ch[0]==fa))
            {
                rot(root);
                ans.push_back(root);
            }
            else
            {
                ans.push_back(fa);
                rot(fa);
            }
        }
        ans.push_back(root);
        rot(root);
    }
    return;
}
*/
void dfs(int root)
{
    splay(root);
    vis[root] = true;
    if (a[root].ch[0])dfs(a[root].ch[0]);
    if (a[root].ch[1])dfs(a[root].ch[1]);
}
int main()
{
    
    scanf("%d", &n);
    root_a = input_tree(a, n);
    root_t = input_tree(t, n);
    dfs(root_a);
    printf("%d\n", ans.size());
    for (auto i : ans)printf("%d\n", i);
}