#include <bits/stdc++.h>
using namespace std;
static const int OFFSET = 10000;
// -------------------------------------------------------------
// Research team – send_message
// -------------------------------------------------------------
// Global state kept across calls.
struct State {
int N = 0;
int LOG = 0;
vector<int> depth; // depth from the root (node 0)
vector<vector<int>> up; // up[j][v] = 2^j ancestor of v
int a = 0; // current diameter endpoint
int b = 0; // current diameter endpoint
int dist = 0; // current diameter length
int stored_a = -1; // endpoint stored at i = N-2
int final_idx = -1;
};
static unique_ptr<State> g_state = nullptr;
static int lca_query(const State& st, int u, int v) {
if (st.depth[u] < st.depth[v]) swap(u, v);
int diff = st.depth[u] - st.depth[v];
for (int bit = 0; diff > 0; ++bit) {
if (diff & 1) u = st.up[bit][u];
diff >>= 1;
}
if (u == v) return u;
for (int k = st.LOG - 1; k >= 0; --k) {
if (st.up[k][u] != st.up[k][v]) {
u = st.up[k][u];
v = st.up[k][v];
}
}
return st.up[0][u];
}
static int dist_query(const State& st, int u, int v) {
int w = lca_query(st, u, v);
return st.depth[u] + st.depth[v] - 2 * st.depth[w];
}
int send_message(int N, int i, int Pi) {
// initialise state on the first call
if (!g_state) {
g_state = make_unique<State>();
g_state->N = N;
g_state->LOG = 0;
while ((1 << g_state->LOG) <= N) ++g_state->LOG;
g_state->depth.assign(N, 0);
g_state->up.assign(g_state->LOG, vector<int>(N, -1));
g_state->a = 0;
g_state->b = 0;
g_state->dist = 0;
g_state->stored_a = -1;
g_state->final_idx = N - 1;
} else {
// ensure the stored N matches
g_state->N = N;
}
State& st = *g_state;
// ---------------------------------------------------------
// Process node i (add edge (i, Pi))
// ---------------------------------------------------------
st.depth[i] = st.depth[Pi] + 1;
st.up[0][i] = Pi;
for (int j = 1; j < st.LOG; ++j) {
int anc = st.up[j - 1][i];
st.up[j][i] = (anc != -1 ? st.up[j - 1][anc] : -1);
}
int a = st.a;
int b = st.b;
int curd = st.dist;
// try to extend the diameter using the new node i
int da = dist_query(st, i, a);
int db = dist_query(st, i, b);
if (da > curd) {
b = i;
curd = da;
} else if (db > curd) {
a = i;
curd = db;
}
st.a = a;
st.b = b;
st.dist = curd;
// ---------------------------------------------------------
// Decide what to send as a message
// ---------------------------------------------------------
// At i = N-2 we store the first endpoint (st.a)
if (i == N - 2) {
st.stored_a = a;
// send a+1 (value 1 .. 20000, never 0)
return a + 1;
}
// At the very last node we send either:
// * w+1 (no change)
// * w+1 + OFFSET (node N-1 becomes an endpoint)
if (i == N - 1) {
int final_node = N - 1;
int w;
bool change;
// Determine whether the new node is an endpoint of the final diameter
if (st.a == final_node) {
w = st.b;
change = true;
} else if (st.b == final_node) {
w = st.a;
change = true;
} else {
w = st.b; // the endpoint that stays unchanged
change = false;
}
if (change) {
// mark that the final node is an endpoint
return w + 1 + OFFSET;
} else {
// no change – the other endpoint is w
return w + 1;
}
}
// all other sites: do not send a message
return 0;
}
// -------------------------------------------------------------
// Museum – longest_path
// -------------------------------------------------------------
pair<int, int> longest_path(vector<int> S) {
int N = (int)S.size();
if (N <= 1) {
return {0, 0};
}
int final_idx = N - 1;
// The last message tells us whether node N-1 is an endpoint of the diameter.
if (S[final_idx] > OFFSET) {
// Change case: the diameter is (w, N-1)
int w = S[final_idx] - OFFSET - 1;
return {w, final_idx};
} else {
// No change: the diameter consists of the two earlier messages
// Find the other non-zero entry (it is the one stored at i = N-2)
int other_val = -1;
for (int idx = 0; idx < N; ++idx) {
if (idx != final_idx && S[idx] != 0) {
other_val = S[idx];
break;
}
}
// For N >= 3 it must exist; for N == 2 the change case above already handled it
int a = other_val - 1;
int b = S[final_idx] - 1;
return {a, b};
}
}
