#include <vector>
#include <algorithm>
using namespace std;
// 倍增LCA及树深维护
static int depth[10005];
static int up[14][10005];
// 在线直径维护状态
static int U_node = 0, V_node = 0, D_tree = 0;
static long long id_val = 0;
static int bit_idx = 0;
// O(log N) 查询两点距离
int get_lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int j = 0; j < 14; j++) {
if ((diff >> j) & 1) u = up[j][u];
}
if (u == v) return u;
for (int j = 13; j >= 0; j--) {
if (up[j][u] != up[j][v]) {
u = up[j][u];
v = up[j][v];
}
}
return up[0][u];
}
int get_dist(int u, int v) {
return depth[u] + depth[v] - 2 * depth[get_lca(u, v)];
}
// 研究团队
int send_message(int N, int i, int Pi) {
// 首次调用复位所有内部状态
if (i == 1) {
depth[0] = 0;
for (int j = 0; j < 14; j++) up[j][0] = 0;
U_node = 0; V_node = 0; D_tree = 0;
id_val = 0; bit_idx = 0;
}
// 倍增表更新
depth[i] = depth[Pi] + 1;
up[0][i] = Pi;
for (int j = 1; j < 14; j++) {
up[j][i] = up[j-1][up[j-1][i]];
}
int dU = get_dist(i, U_node);
int dV = get_dist(i, V_node);
bool increased = false;
int replaced = 0; // 1: 替换V, 2: 替换U
int max_d = max(dU, dV);
// 如果直径严格扩大了，新直径必定包含 i
if (max_d > D_tree) {
increased = true;
D_tree = max_d;
if (dU > dV) {
replaced = 1;
V_node = i;
} else {
replaced = 2;
U_node = i;
}
}
// 在倒数第50步，冻结当时的原始双端点并转化为二进制ID准备发送
if (i == N - 50) {
id_val = U_node * 10000LL + V_node;
bit_idx = 0;
}
// 进入末期 50 步的密集通信窗口阶段
if (i >= N - 50) {
if (increased) {
// 如果遇到突发的直径延长，优先抢占通信周期，11与12态表示端点更迭
return replaced == 1 ? 4 : 3;
} else {
// 否则平静期传输 27 位的原始基底信息
if (bit_idx < 27) {
long long b = (id_val >> bit_idx) & 1;
bit_idx++;
return b + 1; // 转换为 1 或 2，保持 Z <= 4
}
}
}
return 0; // 沉默，遵守严格低 M 约束
}
// 博物馆
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
long long id = 0;
int bit_idx = 0;
int U_update = -1, V_update = -1;
// 解析研究团队通过时序穿插发来的 50 步信号
for (int i = N - 50; i < N; i++) {
int val = S[i];
if (val == 3) {
U_update = i; // 明确获悉 U 被当步端点接替
} else if (val == 4) {
V_update = i; // 明确获悉 V 被当步端点接替
} else if (val == 1 || val == 2) {
if (bit_idx < 27) {
long long b = val - 1;
id |= (b << bit_idx);
bit_idx++;
}
}
}
// 萃取基底端点
int initial_U = id / 10000;
int initial_V = id % 10000;
// 追溯这 50 步中的演化，定夺真实的最终端点
int final_U = (U_update != -1) ? U_update : initial_U;
int final_V = (V_update != -1) ? V_update : initial_V;
return {final_U, final_V};
}
