# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1235343 | spetr | Prize (CEOI22_prize) | C++20 | 0 ms | 0 KiB |
#include <stdio.h>
using namespace std;
#define N 1000000
int n, k, q, t, p[N], dfn[N], dfc, nfd[N], fa[N], hd[N], e[N * 2]
, Ln[N * 2], ii, rt, hld[N], lv[N], dis[N], sz[N];
void add(int u, int v) {
++ii;
e[ii] = v, Ln[ii] = hd[u];
hd[u] = ii;
}
void dfs(int u) {
sz[u] = 1;
for (int v, j = hd[u]; j; j = Ln[j]) {
v = e[j];
lv[v] = lv[u] + 1;
dfs(v);
sz[u] += sz[v];
if (sz[v] > sz[e[hd[u]]]) e[j] = e[hd[u]], e[hd[u]] = v;
}
}
void dfs2(int u) {
nfd[dfn[u] = dfc++] = u;
for (int v, j = hd[u]; j; j = Ln[j]) {
v = e[j];
hld[v] = j == hd[u] ? hld[u]: v;
dfs2(v);
}
}
int lca(int u, int v) {
while (hld[u] != hld[v]) {
if (lv[hld[u]] > lv[hld[v]]) u = fa[hld[u]];
else v = fa[hld[v]];
}
return dfn[u] < dfn[v] ? u: v;
}
int main() {
scanf("%d%d%d%d", &n, &k, &q, &t);
for (int i = 0; i < n; ++i) {
scanf("%d", &fa[i]);
if (fa[i] == -1)
rt = i;
else
add(--fa[i], i);
}
for (int i = 0; i < n; ++i) scanf("%*d");
fa[rt] = rt; hld[rt] = rt;
dfs(rt);
dfs2(rt);
for (int i = 0; i < k; ++i)
printf("%d ", 1 + nfd[i]);
puts("");
fflush(stdout);
for (int i = 1; i <= q; ++i)
printf("? %d %d\n", 1 + rt, 1 + nfd[i]);
puts("!");
fflush(stdout);
for (int i = 1; i <= q; ++i)
scanf("%*d%d%*d%*d\n", dis + nfd[i]);
static int q1[N], q2[N];
for (int i = 0; i < t; ++i)
cin >> q1[i]>> q2[i];
for (int i = 0; i < t; ++i) {
int u, v;
u = q1[i] - 1, v = q2[i] - 1;
int x = dis[u] + dis[v] - 2 * dis[lca(u, v)];
cout << x << " " << x << "\n";
}
fflush(stdout);
return 0;
}