// --------------- migrations.cpp ----------------
#include <bits/stdc++.h>
using namespace std;
namespace { // 〈-- giữ biến giữa các lần gọi
const int MAXN = 10'000 + 5;
const int LOG = 14; // 2^14 = 16384 > 10000
const int GAP = 500; // khoảng giãn thưa khi còn xa cuối
int Nglob = 0; // N của test hiện tại
int depth_ [MAXN];
int up [LOG][MAXN];
int A = 0, B = 0, D = 0; // hai đầu đường kính tạm thời
int lastSentD = -1; // độ dài lần gần nhất đã gửi
int messagesSent = 0; // đếm thông điệp (≤ 50)
// ---------- LCA & distance ----------
inline int climb(int v, int k) {
for (int b = 0; k; ++b, k >>= 1)
if (k & 1) v = up[b][v];
return v;
}
int lca(int u, int v) {
if (depth_[u] < depth_[v]) swap(u, v);
u = climb(u, depth_[u] - depth_[v]);
if (u == v) return u;
for (int b = LOG - 1; b >= 0; --b)
if (up[b][u] != up[b][v]) {
u = up[b][u];
v = up[b][v];
}
return up[0][u];
}
inline int dist(int u, int v) {
int w = lca(u, v);
return depth_[u] + depth_[v] - 2 * depth_[w];
}
} // unnamed namespace
/* --------------------------------------------------
* 1. Hàm của đoàn khảo sát
* -------------------------------------------------- */
int send_message(int N, int i, int Pi) {
if (i == 1) { // khởi tạo lần đầu
Nglob = N;
depth_[0] = 0;
for (int b = 0; b < LOG; ++b) up[b][0] = 0;
}
/* --- cập nhật thông tin cho đỉnh i --- */
depth_[i] = depth_[Pi] + 1;
up[0][i] = Pi;
for (int b = 1; b < LOG; ++b)
up[b][i] = up[b - 1][ up[b - 1][i] ];
/* --- kiểm tra xem đường kính có tăng không --- */
int d1 = dist(i, A);
int d2 = dist(i, B);
bool changed = false;
if (d1 >= d2 && d1 > D) { B = i; D = d1; changed = true; }
else if (d2 > d1 && d2 > D) { A = i; D = d2; changed = true; }
/* --- quyết định có gửi thông điệp --- */
bool sendNow = false;
if (changed && messagesSent < 50) {
int remainingNodes = Nglob - 1 - i; // còn bao nhiêu đỉnh sẽ tới
int remainingBudget = 50 - messagesSent; // còn bao nhiêu thông điệp
if (remainingNodes <= remainingBudget - 1)
sendNow = true; // gần cuối: cứ lần nào tăng là gửi
else if (lastSentD == -1 || D >= lastSentD + GAP)
sendNow = true; // còn xa: giãn thưa
}
if (!sendNow) return 0;
/* --- gửi: mã hoá cặp (U,V) = (i , other) --- */
int other = (A == i ? B : A);
++messagesSent;
lastSentD = D;
return other + 1; // 1 … 10000
}
/* --------------------------------------------------
* 2. Hàm của bảo tàng
* -------------------------------------------------- */
std::pair<int,int> longest_path(std::vector<int> S) {
for (int i = (int)S.size() - 1; i >= 1; --i)
if (S[i] > 0)
return {i, S[i] - 1}; // cặp cuối cùng đã mã hoá đường kính
return {0, 0}; // N = 1
}
