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

不会树旋(比赛时候看着gif图模拟，现学现卖)，不会Splay 依然可通过本题

将被打乱的树和初始树都计算每个结点的深度(定义根节点深度为$11$)，然后按初始树的广度优先搜索顺序枚举所有结点，如果结点当前深度大于其位于初始树上的深度就一直旋转到深度相同位置（每次旋转都会使当前结点深度$-1-1$），这样贪心的由顶至下将所有结点都恢复到原来的深度即可恢复如初。

至于为什么这么做是对的，比赛期间并没有具体证明，第一感觉就是打乱的树是由初始树一步步旋转而来，左旋右旋互为逆操作，所以可以感性的想象深度相同时位置也会恢复如初。

这样每个结点最多旋转$nn$次，总旋转次数$\le n(n+1)\mathrm{/}2\backslash leq\; n(n\; +\; 1)\; /\; 2$，每次都模拟树的左旋或者右旋即可。

//木の葉舞う所に，火は燃ゆる。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <bitset>
#include <ext/rope>
#include <unordered_set>
#include <unordered_map>
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f
#define debug printf("Hello World\n")
#define ios ios::sync_with_stdio(false)
using namespace __gnu_cxx;
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int mod1 = 1e9 + 7, mod2 = 998244353;
const double PI = 3.1415926535898, Ee = 2.718281828459;
const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
inline int read()
{
    int x = 0, f = 1;char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}
const int N = 1000 + 10, M = 1e6 + 10;

int l[N], r[N], L[N], R[N];
int f[N], F[N];
int d[N], D[N];
bool vis[N];

void dfs1(int u, int dis)
{
    if(u == 0) return;
    D[u] = dis;
    dfs1(L[u], dis + 1);
    dfs1(R[u], dis + 1);
}

void dfs2(int u, int dis)
{
    if(u == 0) return;
    d[u] = dis;
    dfs2(l[u], dis + 1);
    dfs2(r[u], dis + 1);
}


void solve()
{
    int n; cin>>n;
    for(int i = 1;i <= n;i ++)
        cin>>L[i]>>R[i], F[L[i]] = i, F[R[i]] = i;
    for(int i = 1;i <= n;i ++)
        cin>>l[i]>>r[i], f[l[i]] = i, f[r[i]] = i;

    int root1 = 0, root2 = 0;
    for(int i = 1;i <= n;i ++)
    {
        if(F[i] == 0) root1 = i;
        if(f[i] == 0) root2 = i;
    }

    dfs1(root1, 1);
    dfs2(root2, 1);

    vector<int> ans;

    for(int i = 1;i <= n;i ++)
    {
        int idx = 0;
        for(int j = 1;j <= n;j ++)
            if(!vis[j] && (idx == 0 || D[j] < D[idx]))
                idx = j;
        vis[idx] = true;
        while(d[idx] > D[idx])
        {
            int fa1 = f[idx];

            if(l[fa1] == idx) // 左子树右旋
            {
                int now = fa1;
                int fa = f[now];
                if(l[fa] == now) l[fa] = l[now];
                else r[fa] = l[now];

                f[now] = idx;
                f[idx] = fa;
                f[r[idx]] = now;

                int temp = r[l[now]];
                r[l[now]] = now;
                l[now] = temp;
            }
            else // 右子树左旋
            {
                int now = fa1;
                int fa = f[now];
                if(l[fa] == now) l[fa] = r[now];
                else r[fa] = r[now];

                f[now] = idx;
                f[idx] = fa;
                f[l[idx]] = now;

                int temp = l[r[now]];
                l[r[now]] = now;
                r[now] = temp;
            }

            d[idx] --;
            ans.push_back(idx);
        }
        int root = 0;
        for(int j = 1;j <= n;j ++)
            if(f[j] == 0) root = j;
        dfs2(root, 1);
    }

    cout<<ans.size()<<endl;
    for(auto &p : ans)
        cout<<p<<endl;
}

signed main()
{
    ios;
    int t = 1; //  cin>>t;
    while (t--) solve();
    return 0;
}