#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e6+5;
int N, K, Q, T;
// Tree information
int P[2][MAXN], root[2];
vector<int> child[2][MAXN];
vector<int> ord[2];
int tin[2][MAXN], tout[2][MAXN], depth[2][MAXN];
int subtree_by_ord[MAXN];
pii init_tree[2*MAXN];
pii tree[8*MAXN];
void dfs(int curtree, int u, int &cte) {
tin[curtree][u] = ++cte;
ord[curtree].push_back(u);
if (curtree == 0) init_tree[cte] = make_pair(depth[curtree][u], u);
for (int v : child[curtree][u]) {
depth[curtree][v] = depth[curtree][u] + 1;
dfs(curtree, v, cte);
++cte;
if (curtree == 0) init_tree[cte] = make_pair(depth[curtree][u], u);
}
tout[curtree][u] = cte;
}
// Utility function to find minimum of two pairs
pii min_pair(const pii &a, const pii &b) {
if (a.first < b.first || (a.first == b.first && a.second < b.second)) return a;
return b;
}
// Build the segment tree
void build(int node, int start, int end) {
if (start == end) {
tree[node] = init_tree[start];
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = min_pair(tree[2 * node], tree[2 * node + 1]);
}
}
// Query the minimum in range [L, R]
pii qry(int node, int start, int end, int L, int R) {
if (R < start || end < L) {
return {INT_MAX, INT_MAX}; // return max pair (acts as neutral for min)
}
if (L <= start && end <= R) {
return tree[node];
}
int mid = (start + end) / 2;
pii left_min = qry(2 * node, start, mid, L, R);
pii right_min = qry(2 * node + 1, mid + 1, end, L, R);
return min_pair(left_min, right_min);
}
int lca(int curtree, int u, int v) {
int l = tin[curtree][u], r = tin[curtree][v];
if (l > r) swap(l, r);
return qry(1, 1, 2*N, l, r).second;
}
bool sort_by_ord1(int u, int v) {
return tin[1][u] < tin[1][v];
}
// Answer recovery
int result[2][MAXN][2];
// Equation graph for tree 1
int distdata[MAXN];
vector<pii> recov_edge[MAXN];
void recover_dfs(int u) {
for (auto [v, w] : recov_edge[u]) {
if (distdata[v] == -1) {
distdata[v] = distdata[u] + w;
recover_dfs(v);
}
}
}
// Euler tour quicksum for tree 2
int qc[3*MAXN];
int qc2[3*MAXN];
// Queries
int query[MAXN][2];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> K >> Q >> T;
for (int i = 1; i <= N; i++) cin >> P[0][i];
for (int i = 1; i <= N; i++) cin >> P[1][i];
for (int i = 1; i <= N; i++) {
if (P[0][i] != -1) child[0][P[0][i]].push_back(i);
else root[0] = i;
if (P[1][i] != -1) child[1][P[1][i]].push_back(i);
else root[1] = i;
}
// Change to 1-based index
ord[0].push_back(0);
ord[1].push_back(1);
{
for (int i = 0; i <= 2*N; i++) {
init_tree[i] = make_pair(INT_MAX, INT_MAX);
}
depth[0][root[0]] = depth[1][root[1]] = 0;
int cte = 0;
dfs(0, root[0], cte);
cte = 0;
dfs(1, root[1], cte);
}
build(1, 1, 2*N);
for (int i = 1; i <= K; i++) subtree_by_ord[i] = ord[0][i];
sort(subtree_by_ord+1, subtree_by_ord+K+1, sort_by_ord1);
// Query
for (int i = 1; i <= K; i++) cout << subtree_by_ord[i] << " ";
cout << "\n";
for (int i = 1; i < K; i++) {
cout << "? " << subtree_by_ord[i] << " " << subtree_by_ord[i+1] << "\n";
}
cout << "!" << endl;
for (int i = 1; i < K; i++) {
cin >> result[0][i][0] >> result[0][i][1] >> result[1][i][0] >> result[1][i][1];
}
// Tree 1 answer recovery
for (int i = 1; i < K; i++) {
int u = subtree_by_ord[i], v = subtree_by_ord[i+1], w1 = result[0][i][0], w2 = result[0][i][1];
int uvlca = lca(0, u, v);
recov_edge[uvlca].emplace_back(u, w1);
recov_edge[u].emplace_back(uvlca, -w1);
recov_edge[uvlca].emplace_back(v, w2);
recov_edge[v].emplace_back(uvlca, -w2);
}
fill(distdata+1, distdata+N+1, -1);
distdata[root[0]] = 0;
recover_dfs(root[0]);
// Tree 2 answer recovery
for (int i = 1; i < K; i++) {
int u = subtree_by_ord[i], v = subtree_by_ord[i+1], w1 = result[1][i][0], w2 = result[1][i][1];
if (tin[1][v] < tout[1][u]) {
qc[tin[1][v]] += w1+w2;
qc2[tout[1][u]] += w1+w2;
} else {
qc[tin[1][v]] += w1+w2;
}
}
for (int i = 1; i <= 3*N; i++) qc[i] += qc[i-1], qc2[i] += qc2[i-1];
for (int i = 1; i <= 3*N; i++) qc2[i] += qc[i];
for (int i = 1; i <= T; i++) cin >> query[i][0] >> query[i][1];
for (int i = 1; i <= T; i++) {
int u = query[i][0], v = query[i][1];
// Tree 1
int uvlca = lca(0, u, v);
//cout << uvlca << ':';
cout << distdata[u] + distdata[v] - 2*distdata[uvlca] << ' ';
// Tree 2;
if (tin[1][u] > tin[1][v]) swap(u, v);
if (tin[1][v] < tout[1][u])
cout << qc[tin[1][v]] - qc[tin[1][u]] << '\n';
else
cout << qc[tin[1][v]] - qc2[tout[1][u]] << '\n';
}
cout << endl;
return 0;
}
/*
9 3 2 3
2 -1 2 1 1 5 1 4 5
9 4 5 5 7 3 -1 3 7
*/
/*
10 0 0 1
0 3 13 5
4 2
2 1
1 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
719 ms |
234128 KB |
Output is correct |
| 2 |
Correct |
715 ms |
235220 KB |
Output is correct |
| 3 |
Runtime error |
382 ms |
181580 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
791 ms |
235960 KB |
Output is correct |
| 2 |
Correct |
682 ms |
233888 KB |
Output is correct |
| 3 |
Runtime error |
443 ms |
181176 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
507 ms |
231176 KB |
Output is correct |
| 2 |
Correct |
584 ms |
230964 KB |
Output is correct |
| 3 |
Runtime error |
317 ms |
176488 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1133 ms |
338864 KB |
Output is correct |
| 2 |
Correct |
1243 ms |
338440 KB |
Output is correct |
| 3 |
Runtime error |
710 ms |
230840 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1402 ms |
342568 KB |
Output is correct |
| 2 |
Correct |
1404 ms |
342448 KB |
Output is correct |
| 3 |
Runtime error |
852 ms |
233996 KB |
Execution killed with signal 13 |
| 4 |
Halted |
0 ms |
0 KB |
- |
