#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
// Sender's global state
static int depth_arr[10005];
static int up[10005][15];
static int U_curr = 0, V_curr = 0;
static int max_dist = 0;
int get_lca(int u, int v) {
if (depth_arr[u] < depth_arr[v]) swap(u, v);
for (int j = 14; j >= 0; --j) {
if (depth_arr[u] - (1 << j) >= depth_arr[v]) {
u = up[u][j];
}
}
if (u == v) return u;
for (int j = 14; j >= 0; --j) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
int get_dist(int u, int v) {
return depth_arr[u] + depth_arr[v] - 2 * depth_arr[get_lca(u, v)];
}
int send_message(int N, int i, int Pi) {
if (i == 1) {
memset(depth_arr, 0, sizeof(depth_arr));
memset(up, 0, sizeof(up));
U_curr = 0;
V_curr = 0;
max_dist = 0;
}
// Update tree structure
depth_arr[i] = depth_arr[Pi] + 1;
up[i][0] = Pi;
for (int j = 1; j <= 14; ++j) {
up[i][j] = up[up[i][j - 1]][j - 1];
}
int dU = get_dist(i, U_curr);
int dV = get_dist(i, V_curr);
bool changed = false;
int other_endpoint = 0;
if (dU > max_dist && dU >= dV) {
max_dist = dU;
V_curr = i;
other_endpoint = U_curr;
changed = true;
} else if (dV > max_dist) {
max_dist = dV;
U_curr = i;
other_endpoint = V_curr;
changed = true;
}
// We only send a message if the diameter strictly increased.
// The index `i` is implicitly known to the Museum as the second endpoint!
// We send `other_endpoint + 1` to ensure the value is >= 1.
if (changed) {
return other_endpoint + 1;
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
int final_U = 0, final_V = 0;
// The Museum simply finds the LAST message sent.
// The index of the message is one endpoint, and the value (minus 1) is the other.
for (int i = 1; i < N; ++i) {
if (S[i] > 0) {
final_V = i;
final_U = S[i] - 1;
}
}
return {final_U, final_V};
}
