#include <bits/stdc++.h>
using namespace std;
// ----- global data (kept between calls of send_message) -----
static int N_global = 0; // number of sites
static int LOG_ = 0; // bit length of N
static vector<int> depth_; // depth of each node
static vector<vector<int>> up_; // up_[node][k] = 2^k ancestor
static vector<int> parent_; // parent[node]
static int diam_u = 0; // one endpoint of current diameter
static int diam_v = 0; // the other endpoint
static int diam_len = 0; // length of current diameter
static int sent_at_n2 = -1; // value sent at site N-2 (a+1)
static vector<int> S_global; // list of messages
static int lca_(int u, int v) {
if (depth_[u] < depth_[v]) swap(u, v);
int diff = depth_[u] - depth_[v];
for (int k = LOG_ - 1; k >= 0; --k) {
if (diff & (1 << k)) {
u = up_[u][k];
}
}
if (u == v) return u;
for (int k = LOG_ - 1; k >= 0; --k) {
if (up_[u][k] != up_[v][k]) {
u = up_[u][k];
v = up_[v][k];
}
}
return up_[u][0];
}
static int distance_(int u, int v) {
int w = lca_(u, v);
return depth_[u] + depth_[v] - 2 * depth_[w];
}
int send_message(int N, int i, int Pi) {
// initialise on the first call
if (N_global == 0) {
N_global = N;
LOG_ = 0;
while ((1 << LOG_) <= N) ++LOG_;
++LOG_; // a bit more than needed
depth_.assign(N, 0);
up_.assign(N, vector<int>(LOG_, -1));
parent_.assign(N, -1);
S_global.assign(N, 0);
diam_u = diam_v = 0;
diam_len = 0;
sent_at_n2 = -1;
}
// store the edge i - Pi
parent_[i] = Pi;
depth_[i] = depth_[Pi] + 1;
up_[i][0] = Pi;
for (int k = 1; k < LOG_; ++k) {
int prev = up_[i][k - 1];
up_[i][k] = (prev != -1 ? up_[prev][k - 1] : -1);
}
// ----- compute distances to current diameter endpoints -----
int d_i_u = distance_(i, diam_u);
int d_i_v = distance_(i, diam_v);
// candidate new diameter
int new_u = diam_u, new_v = diam_v, new_len = diam_len;
if (d_i_u > new_len && d_i_u >= d_i_v) {
new_u = diam_u;
new_v = i;
new_len = d_i_u;
} else if (d_i_v > new_len && d_i_v > d_i_u) {
new_u = i;
new_v = diam_v;
new_len = d_i_v;
}
// ----- site N-2 : store the smaller endpoint of the current diameter -----
if (i == N - 2) {
int a = min(new_u, new_v);
int val = a + 1; // 1 ... 10000
S_global[i] = val;
sent_at_n2 = val;
diam_u = new_u;
diam_v = new_v;
diam_len = new_len;
return val;
}
// ----- site N-1 : send the final information -----
if (i == N - 1) {
int a = min(diam_u, diam_v);
int b = max(diam_u, diam_v);
int cur_len = diam_len; // distance(a,b)
int d_i_a = distance_(i, a);
int d_i_b = distance_(i, b);
int leaf_val = N; // leaf index is N-1, leaf_val = leaf+1 = N
int val2;
if (d_i_a <= cur_len && d_i_b <= cur_len) {
// unchanged diameter
val2 = b + 1; // <= N-1
} else {
// leaf gives a longer diameter
if (d_i_a > cur_len && d_i_a >= d_i_b) {
// new diameter (a, leaf)
val2 = leaf_val; // = N
} else {
// new diameter (b, leaf)
val2 = leaf_val + (b - a); // <= 19998
}
}
S_global[i] = val2;
diam_u = new_u;
diam_v = new_v;
diam_len = new_len;
return val2;
}
// all other sites: no message
S_global[i] = 0;
diam_u = new_u;
diam_v = new_v;
diam_len = new_len;
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int N = (int)S.size();
int leaf_val = N; // leaf index is N-1, stored as leaf+1 = N
// find non-zero entries
vector<pair<int, int>> nz;
for (int idx = 0; idx < N; ++idx) {
if (S[idx] != 0) nz.push_back({idx, S[idx]});
}
if ((int)nz.size() < 2) {
// fallback
return {0, 0};
}
sort(nz.begin(), nz.end());
// the two largest indices are nz[-2] and nz[-1]
auto [i1, val1] = nz[(int)nz.size() - 2];
auto [i2, val2] = nz[(int)nz.size() - 1];
(void)i1;
(void)i2;
int a = val1 - 1; // stored a (the smaller endpoint after N-2)
int U, V;
if (val2 == leaf_val) {
U = a;
V = N - 1;
} else if (val2 > leaf_val) {
// leaf case with the larger original endpoint
U = a + (val2 - leaf_val);
V = N - 1;
} else {
// unchanged case
U = a;
V = val2 - 1;
}
if (U > V) swap(U, V);
return {U, V};
}
