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
#include <bits/stdc++.h>

using namespace std;

#define NDEBUG 1

constexpr int P = 1000000007;
constexpr int MAXN = 500000;
constexpr int NONE = -1;
constexpr int LEFT = 0;
constexpr int RIGHT = 1;

struct Edge {
    int nidx = NONE, len = 0;
};

struct Node {
    int x;
    Edge e[2];
};

Node nodes[2 * MAXN];

int ReadTree(int s, int n)
{
    int root = NONE;
    for (int i = 0; i < n; ++i) {
        int ni = s + i;
        nodes[ni].x = i;
        int p;
        scanf("%d", &p);
        if (p == NONE)
            root = ni;
        else {
            p--;
            nodes[s + p].e[p < i].nidx = ni;
        }
    }
    return root;
}

constexpr int D(int dir) { return 2 * dir - 1; }
constexpr int O(int dir) { return dir ^ 1; }

template <int dir>
int Down(int i, int len = 0) {
    Node& a = nodes[i];
    Edge& e = a.e[dir];
    if (len == e.len)
        return e.nidx;
    assert(len < e.len);
    len++;
    int d = D(dir) * len;
    int j = i + d;
    Node& b = nodes[j];
    b.x = a.x + d;
    b.e[dir] = Edge{e.nidx, e.len - len};
    b.e[O(dir)] = Edge();
    return j;
}

int Align(int i, int j);

template <int dir>
int AlignDown(int i, int j) {
    Edge& e = nodes[i].e[dir];
    Edge& f = nodes[j].e[dir];
    int len = min(e.len, f.len);
    return Align(Down<dir>(i, len), Down<dir>(j, len));
}

template <int dir>
int Rotate(Edge& e) {
    int j = e.nidx;
    Node& a = nodes[j];
    assert(a.e[O(dir)].nidx == NONE);
    int res = a.e[O(dir)].len;
    e.len += res + 1 + a.e[dir].len;
    e.nidx = a.e[dir].nidx;
    return res;
}

int Path(int i, int y, int z);

template <int dir>
int PathDown(int i, int y) {
    Node& a = nodes[i];
    int len = (y - a.x) * D(dir);
    Edge& e = a.e[dir];
    if (e.len >= len)
        return 0;
    int j = e.nidx;
    int z = a.x + D(dir) * (e.len + 1);
    int res = dir == LEFT ? Path(j, y, z) : Path(j, z, y);
    return (res + Rotate<dir>(e)) % P;
}

int Path(int i, int y, int z) {
    return (PathDown<LEFT>(i, y) + PathDown<RIGHT>(i, z)) % P;
}

int Align(int i, int j) {
    if (i == NONE) {
        assert(j == NONE);
        return 0;
    }
    if (nodes[i].x > nodes[j].x) swap(i, j);
    Node& a = nodes[i];
    Node& b = nodes[j];
    if (a.x == b.x)
        return (AlignDown<LEFT>(i, j) + AlignDown<RIGHT>(i, j)) % P;
    assert(a.x < b.x);
    int res = (Path(i, a.x, b.x) + Path(j, a.x, b.x)) % P;
    int len = b.x - a.x;
    res = (res + len) % P;
    int rec_res = (Align(Down<LEFT>(i), Down<LEFT>(j, len)) +
                   Align(Down<RIGHT>(i, len), Down<RIGHT>(j))) % P;
    return (res + rec_res) % P;
}

int main() {
    int n;
    scanf("%d", &n);
    int a = ReadTree(0, n);
    int b = ReadTree(n, n);
    printf("%d\n", Align(a, b));
    return 0;
}