#include <iostream>
#include <vector>
#include <algorithm>
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;
static int U_prev = 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) {
U_curr = 0;
V_curr = 0;
max_dist = 0;
depth_arr[0] = 0;
for (int j = 0; j <= 14; ++j) up[0][j] = 0;
}
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);
// Strictly track the true online diameter
if (dU > max_dist || dV > max_dist) {
if (dU >= dV) {
V_curr = i;
max_dist = dU;
} else {
U_curr = i;
max_dist = dV;
}
}
// Delay all communication until the final two steps
if (i == N - 2) {
U_prev = U_curr;
return U_curr + 1;
} else if (i == N - 1) {
if (U_curr == U_prev) {
// U survived, so the other endpoint is V_curr
return V_curr + 1;
} else {
// U was replaced by N-1. To signal this, we add 10000 to V_curr
return V_curr + 10001;
}
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
// The Museum only needs to look at the very last two messages
int val1 = S[N - 2];
int val2 = S[N - 1];
int U = val1 - 1;
int V = 0;
if (val2 > 10000) {
V = val2 - 10001;
U = N - 1; // U was replaced by the final node
} else {
V = val2 - 1;
}
return {U, V};
}
