#include <bits/stdc++.h>
using namespace std;
// ---- globals mirroring the Python code ----
static vector<int> g_depth; // depths, size N
static vector<vector<int>> g_anc; // binary lifting table, N x LOG
static int g_deepest = 0; // index of deepest leaf so far
static int g_N = -1;
static int g_LOG = 0;
static bool g_inited = false;
static void init_case(int N) {
g_N = N;
// Python: _LOG = (N - 1).bit_length() + 1
// bit_length(x) = floor(log2(x)) + 1 for x>0; for N>=1, (N-1) may be 0.
// Implement safely:
int x = N - 1;
int bitlen = 0;
while (x > 0) { bitlen++; x >>= 1; }
g_LOG = bitlen + 1;
g_depth.assign(N, -1);
g_anc.assign(N, vector<int>(g_LOG, -1));
g_depth[0] = 0; // root depth
g_deepest = 0;
g_inited = true;
}
// Signature not requested by you, but included to match the Python behavior.
int send_message(int N, int i, int Pi) {
if (!g_inited) init_case(N);
// update tree info for vertex i
g_depth[i] = g_depth[Pi] + 1;
g_anc[i][0] = Pi;
for (int k = 1; k < g_LOG; k++) {
int prev = g_anc[i][k - 1];
g_anc[i][k] = (prev != -1) ? g_anc[prev][k - 1] : -1;
}
// maintain deepest leaf
if (g_depth[i] > g_depth[g_deepest]) g_deepest = i;
// decide message
if (N >= 3 && i == N - 2) {
return (g_deepest / 100) + 1; // 1..100
} else if (i == N - 1) {
if (g_deepest == i) return 101; // sentinel
return (g_deepest % 100) + 1; // 1..100
} else {
return 0;
}
}
// ---- requested header ----
std::pair<int,int> longest_path(std::vector<int> S) {
int N = (int)S.size();
// sentinel case
if (S[N - 1] == 101) {
return {0, N - 1};
}
// normal case (N >= 3): hi/lo encode deepest
if (N >= 3) {
int hi = S[N - 2]; // 1..100
int lo = S[N - 1]; // 1..100
int deepest = (hi - 1) * 100 + (lo - 1);
return {0, deepest};
} else {
// N == 2
return {0, S[1] - 1};
}
}
