1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <vector>
using namespace std;

struct Tree{
    struct Node{
        int parent, left, right;
    };
    vector<Node>V;

    Tree(int n):V(n+1, Node{-1,-1,-1}){}

    friend istream& operator>>(istream& is, Tree& tree){
        tree.V[0] = Node{-1, -1, -1};

        for(int i=1;i<(int)tree.V.size();i++){
            int p;
            cin >> p;
            if(p!=-1){
                tree.V[i].parent = p;
                if(i<p)
                    tree.V[p].left = i;
                else
                    tree.V[p].right = i;
            }
            else{
                tree.V[i].parent = 0;
                tree.V[0].left = i;
            }
        }
        return is;
    }

    int& get_parent_link(int v){
        return (V[V[v].parent].left==v) ? V[V[v].parent].left : V[V[v].parent].right ;
    }

    bool rotate_left(int v){
        int w = V[v].right;
        if(w==-1 || V[w].left!=-1)
            return false;

        get_parent_link(v)=w;
        V[w].parent = V[v].parent;
        V[v].parent = w;
        V[w].left = v;
        V[v].right = -1;

        return true;
    }
    bool rotate_right(int v){
        int w = V[v].left;
        if(w==-1 || V[w].right!=-1)
            return false;

        get_parent_link(v)=w;
        V[w].parent = V[v].parent;
        V[v].parent = w;
        V[w].right = v;
        V[v].left = -1;

        return true;
    }

    int find_root()const{
        return V[0].left;
    }

    int clear_left_subtree(int v){
        int& pLink = get_parent_link(v);

        int rotations=0;
        while(true){
            if(V[pLink].left==-1)
                break;
            rotations += clear_right_subtree(V[pLink].left);
            rotate_right(pLink);
            rotations++;
        }

        return rotations;
    }
    int clear_right_subtree(int v){
        int& pLink = get_parent_link(v);

        int rotations=0;
        while(true){
            if(V[pLink].right==-1)
                break;
            rotations += clear_left_subtree(V[pLink].right);
            rotate_left(pLink);
            rotations++;
        }

        return rotations;
    }

    int rewind_left(int v, int target){
        int& pLink = get_parent_link(v);

        int rotations=0;
        while(true){
            if(pLink==target)
                break;
            rotations += clear_left_subtree(V[pLink].right);
            rotate_left(pLink);
            rotations++;
        }

        return rotations;
    }
    int rewind_right(int v, int target){
        int& pLink = get_parent_link(v);

        int rotations=0;
        while(true){
            if(pLink==target)
                break;
            rotations += clear_right_subtree(V[pLink].left);
            rotate_right(pLink);
            rotations++;
        }

        return rotations;
    }

    int reroot(int v, int target){
        if(v==target)
            return 0;
        if(target<v)
            return rewind_right(v, target);
        return rewind_left(v, target);
    }
};

int transform(Tree& t1, const Tree& t2, int r1, int r2){
    int rotations=t1.reroot(r1, r2);
    if(t1.V[r2].left!=-1)
        rotations += transform(t1, t2, t1.V[r2].left, t2.V[r2].left);
    if(t1.V[r2].right!=-1)
        rotations += transform(t1, t2, t1.V[r2].right, t2.V[r2].right);
    return rotations;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    Tree t1(n),t2(n);
    cin >> t1 >> t2;

    int result = transform(t1, t2, t1.find_root(), t2.find_root());
    cout << result << "\n";

    return 0;
}