#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}; } }