#define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) constexpr int MOD = 1e9+7; ll modPow(ll a, ll e, ll m) { ll t = 1 % m; while (e) { if (e % 2) t = t*a % m; e /= 2; a = a*a % m; } return t; } struct Zp { ll x; Zp() : x(0) {} Zp(ll a) : x(a%MOD) { if (x < 0) x += MOD; } #define OP(c,d) Zp& operator c##=(Zp r) { x = x d; return *this; } Zp operator c(Zp r) const { Zp t = *this; return t c##= r; } OP(+, +r.x - MOD*(x+r.x >= MOD)); OP(-, -r.x + MOD*(x-r.x < 0)); OP(*, *r.x % MOD); OP(/, *r.inv().x % MOD); Zp inv() const { return pow(MOD-2); } Zp pow(ll e) const{ return modPow(x,e,MOD); } void print() { cerr << x; } }; Vi E[2], siz; int child(int v, int c) { return v != -1 ? E[c][v] : -1; } int size(int v) { return v != -1 ? siz[v] : 0; } Zp solve(int u, int v, bool uf, bool vf) { if (u == -1 && v == -1) { return 0; } int us = size(u), vs = size(v); int ul = child(u, uf), ur = child(u, !uf); int vl = child(v, vf), vr = child(v, !vf); if (us > vs) { return solve(ul, v, uf, vf) + solve(ur, -1, !uf, 0) + size(ur); } else if (us < vs) { return solve(u, vl, uf, vf) + solve(vr, -1, !vf, 0) + size(vr); } else { return solve(ul, vl, uf, vf) + solve(ur, vr, !uf, !vf) + abs(size(ul) - size(vl)); } } void computeSizes(int v) { siz[v] = 1; rep(c, 0, 2) { int e = E[c][v]; if (e != -1) { computeSizes(e); siz[v] += siz[e]; } } } int loadTree(int n, int offset) { int root = -1; rep(i, 0, n) { int j; cin >> j; j--; if (j == -2) { root = i+offset; } else { E[i>j][j+offset] = i+offset; } } computeSizes(root); return root; } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int n; cin >> n; E[0].resize(n*2, -1); E[1].resize(n*2, -1); siz.resize(n*2); int u = loadTree(n, 0); int v = loadTree(n, n); cout << solve(u, v, 0, 0).x << '\n'; return 0; }
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 | #define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) constexpr int MOD = 1e9+7; ll modPow(ll a, ll e, ll m) { ll t = 1 % m; while (e) { if (e % 2) t = t*a % m; e /= 2; a = a*a % m; } return t; } struct Zp { ll x; Zp() : x(0) {} Zp(ll a) : x(a%MOD) { if (x < 0) x += MOD; } #define OP(c,d) Zp& operator c##=(Zp r) { x = x d; return *this; } Zp operator c(Zp r) const { Zp t = *this; return t c##= r; } OP(+, +r.x - MOD*(x+r.x >= MOD)); OP(-, -r.x + MOD*(x-r.x < 0)); OP(*, *r.x % MOD); OP(/, *r.inv().x % MOD); Zp inv() const { return pow(MOD-2); } Zp pow(ll e) const{ return modPow(x,e,MOD); } void print() { cerr << x; } }; Vi E[2], siz; int child(int v, int c) { return v != -1 ? E[c][v] : -1; } int size(int v) { return v != -1 ? siz[v] : 0; } Zp solve(int u, int v, bool uf, bool vf) { if (u == -1 && v == -1) { return 0; } int us = size(u), vs = size(v); int ul = child(u, uf), ur = child(u, !uf); int vl = child(v, vf), vr = child(v, !vf); if (us > vs) { return solve(ul, v, uf, vf) + solve(ur, -1, !uf, 0) + size(ur); } else if (us < vs) { return solve(u, vl, uf, vf) + solve(vr, -1, !vf, 0) + size(vr); } else { return solve(ul, vl, uf, vf) + solve(ur, vr, !uf, !vf) + abs(size(ul) - size(vl)); } } void computeSizes(int v) { siz[v] = 1; rep(c, 0, 2) { int e = E[c][v]; if (e != -1) { computeSizes(e); siz[v] += siz[e]; } } } int loadTree(int n, int offset) { int root = -1; rep(i, 0, n) { int j; cin >> j; j--; if (j == -2) { root = i+offset; } else { E[i>j][j+offset] = i+offset; } } computeSizes(root); return root; } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int n; cin >> n; E[0].resize(n*2, -1); E[1].resize(n*2, -1); siz.resize(n*2); int u = loadTree(n, 0); int v = loadTree(n, n); cout << solve(u, v, 0, 0).x << '\n'; return 0; } |