#include <iostream>
#include <vector>
using namespace std;
int N, K, Q, T, koren, _, H;
vector<int> rodice;
vector<vector<int>> synove;
vector<int> mnozina;
vector<bool> mnozina_b;
vector<int> vahy;
vector<int> hladiny;
vector<int> vzdalenost;
vector<vector<int>> skocky;
void vytvor_mnozinu(int v) {
if (mnozina.size() < K) {
mnozina.push_back(v);
}
for (int s:synove[v]) {
hladiny[s] = hladiny[v] + 1;
vytvor_mnozinu(s);
}
}
void pocitej_vzdalenost(int v) {
for (int s: synove[v]) if (mnozina_b[s]) {
vzdalenost[s] = vzdalenost[v] + vahy[s];
// cout << "vzdalenost[" << s << "] = " << vzdalenost[s] << endl;
pocitej_vzdalenost(s);
}
}
int hledej_vidlicku(int a, int b, int h) {
// cout << "Hledej_vidlicku(" << a << ", " << b << ", " << h << ");\n";
if (h == -1) {
return a;
} else {
int a_ = ((skocky[h][a] == -1) ? -1 : (skocky[h][rodice[skocky[h][a]]]));
int b_ = ((skocky[h][b] == -1) ? -1 : (skocky[h][rodice[skocky[h][b]]]));
if (a_ == b_) {
return hledej_vidlicku(a, b, h - 1);
} else {
return hledej_vidlicku(a_, b_, h - 1);
}
}
}
int vidlicka(int a, int b) {
if (hladiny[b] > hladiny[a]) {
return vidlicka(b, a);
}
int hh = 1, h = 0;
while (hladiny[a] != hladiny[b]) {
if ((hladiny[a] - hladiny[b]) % (2 * hh) != 0) {
a = skocky[h][a];
}
h++;
hh *= 2;
}
return hledej_vidlicku(a, b, H - 2);
}
int main() {
cin >> N >> K >> Q >> T;
rodice.resize(N);
for (int i = 0; i < N; i++) {
cin >> rodice[i];
if (rodice[i] == -1) {
koren = i;
} else {
rodice[i]--;
}
}
for (int i = 0; i < N; i++) {
cin >> _;
}
synove.resize(N);
for (int i = 0; i < N; i++) {
synove[i].resize(0);
}
for (int i = 0; i < N; i++) if (i != koren) {
synove[rodice[i]].push_back(i);
}
hladiny.resize(N);
hladiny[koren] = 0;
vytvor_mnozinu(koren);
for (int i = 0; i < K; i++) {
cout << mnozina[i] + 1 << ((i != K - 1) ? ' ' : '\n');
}
for (int i = 1; i < K; i++) {
cout << "? " << rodice[mnozina[i]] + 1 << ' ' << mnozina[i] + 1 << endl;
}
cout << "!\n";
flush(cout);
cout.flush();
vahy.resize(N);
for (int i = 1; i < K; i++) {
cin >> _ >> _ >> _ >> _;
vahy[mnozina[i]] = _;
}
H = 1;
int hh = 1;
while (hh < N - 1) {
H++;
hh *= 2;
}
skocky.resize(H);
skocky[0].resize(N);
for (int i = 0; i < N; i++) {
skocky[0][i] = rodice[i];
}
for (int h = 1; h < H; h++) {
skocky[h].resize(N);
for (int i = 0; i < N; i++) {
skocky[h][i] = ((skocky[h - 1][i] == -1) ? -1 : (skocky[h - 1][skocky[h - 1][i]]));
}
}
mnozina_b.resize(N);
for (int i = 0; i < N; i++) {
mnozina_b[i] = false;
}
for (int x: mnozina) {
mnozina_b[x] = true;
}
vzdalenost.resize(N);
vzdalenost[koren] = 0;
pocitej_vzdalenost(koren);
for (int t = 0; t < T; t++) {
int a, b;
cin >> a >> b; a--; b--;
int c = vidlicka(a, b);
// cout << "vidlicka(" << a << ", " << b << ") = " << c << endl;
cout << vzdalenost[a] + vzdalenost[b] - 2 * vzdalenost[c] << ' ' << vzdalenost[a] + vzdalenost[b] - 2 * vzdalenost[c] << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |