#include "migrations.h"
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
const int MOD = 20000; // maximum message value
const int LOG = 14; // 2^14 = 16384 > 10000
int N_global; // actual number of sites, set on first call
int parent[10000]; // parent index, parent[0] = 0
int depth[10000]; // distance from root
int up[LOG][10000]; // binary lifting table
int curA, curB; // current diameter endpoints (curA < curB)
int stored_rank; // rank of (curA,curB) after processing N-2
// ----------------------------------------------------------------------
// LCA and distance
// ----------------------------------------------------------------------
static void lca_init(int v) {
if (v != 0) {
up[0][v] = parent[v];
for (int k = 1; k < LOG; ++k)
up[k][v] = up[k-1][ up[k-1][v] ];
}
}
static int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; ++k)
if (diff & (1 << k))
u = up[k][u];
if (u == v) return u;
for (int k = LOG-1; k >= 0; --k)
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
return up[0][u];
}
static int dist(int u, int v) {
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}
// ----------------------------------------------------------------------
// Ranking of unordered pairs (a,b) with 0 <= a < b < N
// ----------------------------------------------------------------------
static long long cumulative_before(int a, int N) {
return (long long)a * N - (long long)a * (a + 1) / 2;
}
static int rank_pair(int a, int b, int N) {
// a < b guaranteed
return (int)(cumulative_before(a, N) + (b - a - 1));
}
static pair<int, int> unrank(int r, int N) {
long long cum = 0;
int a = 0;
while (true) {
int cnt = N - a - 1; // number of b for this a
if (r < cum + cnt) {
int b = a + 1 + (r - cum);
return {a, b};
}
cum += cnt;
++a;
}
}
// ----------------------------------------------------------------------
// Research team's procedure
// ----------------------------------------------------------------------
int send_message(int N, int i, int Pi) {
static bool init = false;
if (!init) {
init = true;
N_global = N; // store for later ranking
depth[0] = 0;
parent[0] = 0;
for (int k = 0; k < LOG; ++k) up[k][0] = 0;
curA = curB = 0;
}
// ----- insert node i -----
parent[i] = Pi;
depth[i] = depth[Pi] + 1;
lca_init(i);
// ----- update current diameter -----
int dAB = dist(curA, curB);
int dA = dist(curA, i);
int dB = dist(curB, i);
if (dA > dAB && dA >= dB) { // (curA, i) becomes new diameter
curA = curA;
curB = i;
} else if (dB > dAB) { // (curB, i) becomes new diameter
curA = curB;
curB = i;
}
if (curA > curB) swap(curA, curB); // keep curA < curB
// ----- decide what to send -----
if (i < N - 2) {
return 0; // no message
}
else if (i == N - 2) {
// store the rank of the current diameter endpoints
stored_rank = rank_pair(curA, curB, N_global);
int bucket = stored_rank % MOD;
return bucket + 1; // message in {1..MOD}
}
else { // i == N - 1
// use the state before adding i (stored_rank)
auto [a, b] = unrank(stored_rank, N_global); // a < b
int dA = dist(a, i);
int dB = dist(b, i);
int dAB = dist(a, b);
int case_val = 0;
if (dA > dAB && dA >= dB) case_val = 1;
else if (dB > dAB) case_val = 2;
int q = stored_rank / MOD;
int V2 = q * 3 + case_val + 1; // 1 .. q*3+3
return V2;
}
}
// ----------------------------------------------------------------------
// Museum's procedure
// ----------------------------------------------------------------------
pair<int, int> longest_path(vector<int> S) {
int N = S.size(); // = 10000
int bucket = S[N-2] - 1;
int V2 = S[N-1];
int q = (V2 - 1) / 3;
int case_val = (V2 - 1) % 3;
int rank = q * MOD + bucket;
auto [a, b] = unrank(rank, N);
if (case_val == 0)
return {a, b};
else if (case_val == 1)
return {a, N-1};
else
return {b, N-1};
}
