#include <bits/stdc++.h> using namespace std; typedef long long int LL; const int MAXN = 300005; const int INF = 1000000001; const LL M = 1000000007LL; int A[MAXN]; int parent[MAXN]; vector<int> adj[MAXN]; queue<int> Q; int d[2][MAXN]; int n, N = 1; bool alice_compare(int x, int y) { int diffx = d[0][x] + d[1][x]; int diffy = d[0][y] + d[1][y]; if (diffx != diffy) return diffx > diffy; if (d[0][x] != d[0][y]) return d[0][x] > d[0][y]; if (d[1][x] != d[1][y]) return d[1][x] > d[1][y]; return x > y; } int pos_alice = 0; vector<int> alice_options; void go(int lvl) { if (lvl == n) return; int u = N; for (int i = 0; i < A[lvl]; i++) { N++; int v = N; adj[u].push_back(v); adj[v].push_back(u); parent[v] = u; go(lvl+1); } } pair<int,int> indices(int a, int b, int c) { int u = 1; for (int lvl = 1; lvl < c; lvl++) { for (int v : adj[u]) if (v != parent[u]) { u = v; break; } } int au = u, bu = u; if (a != c) { for (int v : adj[u]) if (v != parent[u]) { au = v; break; } } if (b != c) { int cnt = 0; for (int v : adj[c]) if (v != parent[u]) { cnt++; if (cnt == 2) { bu = v; break; } } } for (int lvl = c+1; lvl < a; lvl++) { for (int v : adj[au]) if (v != parent[au]) { au = v; break; } } for (int lvl = c+1; lvl < b; lvl++) { for (int v : adj[bu]) if (v != parent[bu]) { bu = v; break; } } return make_pair(au, bu); } void bfs(int st, int x) { fill(d[st], d[st]+N+1, INF); d[st][x] = 0; Q.push(x); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int v : adj[u]) if (d[st][v] == INF) { d[st][v] = d[st][u] + 1; Q.push(v); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int q; cin >> n >> q; for (int i = 1; i < n; i++) cin >> A[i]; go(1); while (q--) { int a, b, c; cin >> a >> b >> c; pair<int,int> idx = indices(a, b, c); bfs(0, idx.first); bfs(1, idx.second); alice_options = vector<int>(N); for (int i = 1; i <= N; i++) alice_options[i-1] = i; sort(alice_options.begin(), alice_options.end(), alice_compare); /* cerr << "Alice order: "; for (int x : alice_options) cerr << x << " "; cerr << "\n"; cerr << "Bob order: "; for (int x : bob_options) cerr << x << " "; cerr << "\n"; */ LL result = 0; for (int i = 0; i < alice_options.size(); i++) { if (i % 2 == 0) result = (result + d[0][alice_options[i]]) % M; else result = (result - d[1][alice_options[i]] + M) % M; } cout << result << "\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 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; typedef long long int LL; const int MAXN = 300005; const int INF = 1000000001; const LL M = 1000000007LL; int A[MAXN]; int parent[MAXN]; vector<int> adj[MAXN]; queue<int> Q; int d[2][MAXN]; int n, N = 1; bool alice_compare(int x, int y) { int diffx = d[0][x] + d[1][x]; int diffy = d[0][y] + d[1][y]; if (diffx != diffy) return diffx > diffy; if (d[0][x] != d[0][y]) return d[0][x] > d[0][y]; if (d[1][x] != d[1][y]) return d[1][x] > d[1][y]; return x > y; } int pos_alice = 0; vector<int> alice_options; void go(int lvl) { if (lvl == n) return; int u = N; for (int i = 0; i < A[lvl]; i++) { N++; int v = N; adj[u].push_back(v); adj[v].push_back(u); parent[v] = u; go(lvl+1); } } pair<int,int> indices(int a, int b, int c) { int u = 1; for (int lvl = 1; lvl < c; lvl++) { for (int v : adj[u]) if (v != parent[u]) { u = v; break; } } int au = u, bu = u; if (a != c) { for (int v : adj[u]) if (v != parent[u]) { au = v; break; } } if (b != c) { int cnt = 0; for (int v : adj[c]) if (v != parent[u]) { cnt++; if (cnt == 2) { bu = v; break; } } } for (int lvl = c+1; lvl < a; lvl++) { for (int v : adj[au]) if (v != parent[au]) { au = v; break; } } for (int lvl = c+1; lvl < b; lvl++) { for (int v : adj[bu]) if (v != parent[bu]) { bu = v; break; } } return make_pair(au, bu); } void bfs(int st, int x) { fill(d[st], d[st]+N+1, INF); d[st][x] = 0; Q.push(x); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int v : adj[u]) if (d[st][v] == INF) { d[st][v] = d[st][u] + 1; Q.push(v); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int q; cin >> n >> q; for (int i = 1; i < n; i++) cin >> A[i]; go(1); while (q--) { int a, b, c; cin >> a >> b >> c; pair<int,int> idx = indices(a, b, c); bfs(0, idx.first); bfs(1, idx.second); alice_options = vector<int>(N); for (int i = 1; i <= N; i++) alice_options[i-1] = i; sort(alice_options.begin(), alice_options.end(), alice_compare); /* cerr << "Alice order: "; for (int x : alice_options) cerr << x << " "; cerr << "\n"; cerr << "Bob order: "; for (int x : bob_options) cerr << x << " "; cerr << "\n"; */ LL result = 0; for (int i = 0; i < alice_options.size(); i++) { if (i % 2 == 0) result = (result + d[0][alice_options[i]]) % M; else result = (result - d[1][alice_options[i]] + M) % M; } cout << result << "\n"; } return 0; } |