#include <bits/stdc++.h>
using namespace std;
const int LOG = 15; // 2^14 = 16384 > 10000
// ---------- global state for the incremental construction ----------
static int gN = -1;
static vector<int> gDepth;
static vector<array<int, LOG>> gUp;
static int gA = 0, gB = 0, gD = 0; // current diameter endpoints and length
static int gAprev = -1, gBprev = -1; // endpoints after processing N-2
// ---------- LCA utilities ----------
int lca(int u, int v) {
if (gDepth[u] < gDepth[v]) swap(u, v);
int diff = gDepth[u] - gDepth[v];
for (int k = LOG - 1; k >= 0; --k)
if (diff & (1 << k))
u = gUp[u][k];
if (u == v) return u;
for (int k = LOG - 1; k >= 0; --k) {
if (gUp[u][k] != gUp[v][k]) {
u = gUp[u][k];
v = gUp[v][k];
}
}
return gUp[u][0];
}
int dist(int u, int v) {
int w = lca(u, v);
return gDepth[u] + gDepth[v] - 2 * gDepth[w];
}
// ---------- send_message implementation ----------
int send_message(int N, int i, int Pi) {
// (re)initialise for a new test case
if (gN != N) {
gN = N;
gDepth.assign(N, 0);
gUp.assign(N, array<int, LOG>());
for (int k = 0; k < LOG; ++k) gUp[0][k] = 0;
gA = gB = 0;
gD = 0;
gAprev = gBprev = -1;
}
// set depth and binary lifting ancestors for node i
gDepth[i] = gDepth[Pi] + 1;
gUp[i][0] = Pi;
for (int k = 1; k < LOG; ++k)
gUp[i][k] = gUp[gUp[i][k - 1]][k - 1];
// update the diameter using the new node i
int da = dist(i, gA);
int db = dist(i, gB);
if (da > gD) {
gB = i;
gD = da;
} else if (db > gD) {
gA = i;
gD = db;
}
// node N-2: remember the current endpoints and send the first endpoint
if (i == N - 2) {
gAprev = gA;
gBprev = gB;
return gA + 1; // encode a+1 (always 1..10000)
}
// node N-1: we now know the final diameter, encode the second endpoint / flag
if (i == N - 1) {
bool unchanged = ( (gA == gAprev && gB == gBprev) ||
(gA == gBprev && gB == gAprev) );
if (unchanged) {
// unchanged: send bprev+1 (<=10000)
return gBprev + 1;
} else if ( (gA == N - 1 && gB == gAprev) ||
(gB == N - 1 && gA == gAprev) ) {
// new leaf paired with a_prev -> (N-1, a_prev)
// encode by sending nothing
return 0;
} else {
// new leaf paired with b_prev -> (N-1, b_prev)
// encode as bprev + 10001 (range 10001..19999)
return gBprev + 10001;
}
}
// any other node: we do not send a message
return 0;
}
// ---------- longest_path implementation ----------
pair<int, int> longest_path(vector<int> S) {
int N = (int)S.size(); // S[0] is always 0
int a = S[N - 2] - 1; // first endpoint stored at N-2
int v = S[N - 1]; // second part / flag
int u, w;
if (v == 0) { // (N-1, a)
u = a;
w = N - 1;
} else if (v <= 10000) { // unchanged case (a, b)
u = a;
w = v - 1;
} else { // (N-1, b)
u = N - 1;
w = v - 10001;
}
return {u, w};
}
