#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;
int max_d = max(dU, dV);
// 动态直径贪心更迭机制
if (max_d > D_tree) {
increased = true;
D_tree = max_d;
if (dU > dV) {
replaced = 1;
V_node = i;
} else if (dV > dU) {
replaced = 2;
U_node = i;
} else { // dU == dV，绝对偏袒保留 0
if (U_node == 0) {
replaced = 1;
V_node = i;
} else if (V_node == 0) {
replaced = 2;
U_node = i;
} else {
replaced = 1;
V_node = i;
}
}
}
// 在 N-50 步，冻结进入密文模式前最终始的基础直径端点身份
if (i == N - 50) {
// 将包含 0 的端点强制交换至 U_node
if (V_node == 0) {
swap(U_node, V_node);
if (increased) replaced = 3 - replaced;
}
// U 位于低 14 位，V 位于高 14 位
id_val = V_node * 16384LL + U_node;
bit_idx = 0;
}
// ====== 传输层 (M <= 50) ======
if (i >= N - 50) {
if (increased) {
// 事件抢占帧：3 代表 V 被更新，4 代表 U 被更新
return replaced == 1 ? 3 : 4;
} else {
// 平静期发送数据帧
if (bit_idx < 28) {
long long b = (id_val >> bit_idx) & 1;
bit_idx++;
return b + 1; // 发送 1(对于位0) 或 2(对于位1)
}
}
}
return 0; // 前 9950 步保持彻底静默，规避通信代价 M
}
// ================== 博物馆 ==================
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
long long id = 0;
int final_U = -1, final_V = -1;
int b_idx = 0;
// 从最后 50 步的信号列恢复真相
for (int i = N - 50; i < N; i++) {
if (i < 0) continue; // 边界保护
int val = S[i];
if (val == 0) continue;
if (val == 3) {
final_V = i; // 更新事件信号
} else if (val == 4) {
final_U = i; // 更新事件信号
} else if (val == 1 || val == 2) {
if (b_idx < 28) { // 组装基础数据位
id |= ((long long)(val - 1) << b_idx);
b_idx++;
}
}
}
// 解析底座 (低 14 位 为 U，高 14 位 为 V)
int initial_U = id % 16384;
int initial_V = id / 16384;
// 如果无抢占事件，沿用底座恢复结果
if (final_U == -1) final_U = initial_U;
if (final_V == -1) final_V = initial_V;
return {final_U, final_V};
}
