#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
int send_message(int N, int i, int Pi) {
// ---------- static data kept between calls ----------
static bool initialized = false;
static int N_glob, LOG, startIdx;
static vector<int> depth;
static vector<array<int, 15>> up; // LOG ≤ 14 for N ≤ 10000
static int a, b, diam; // current diameter ends and length
static bool initDone; // have we sent the first init message ?
static bool pendingSecond; // second init still waiting ?
static int pendingSecondVal; // its value (b+1)
static bool firstCall = true;
if (!initialized) {
N_glob = N;
LOG = 0;
while ((1 << LOG) <= N_glob) ++LOG; // LOG = ceil(log2(N+1))
depth.assign(N_glob, 0);
up.assign(N_glob, array<int,15>{});
for (int k = 0; k < LOG; ++k) up[0][k] = 0;
a = b = 0;
diam = 0;
startIdx = max(1, N_glob - 50); // first vertex of the suffix
initDone = false;
pendingSecond = false;
pendingSecondVal = 0;
initialized = true;
}
// ----- store depth and ancestors of vertex i -----
depth[i] = depth[Pi] + 1;
up[i][0] = Pi;
for (int k = 1; k < LOG; ++k)
up[i][k] = up[ up[i][k-1] ][k-1];
// ----- auxiliary LCA / distance functions -----
auto 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[u][k];
if (u == v) return u;
for (int k = LOG - 1; k >= 0; --k)
if (up[u][k] != up[v][k]) {
u = up[u][k];
v = up[v][k];
}
return up[u][0];
};
auto dist = [&](int u, int v) {
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
};
// ----- evaluate possible diameter change -----
int du = dist(i, a);
int dv = dist(i, b);
bool changed = false;
int other = -1; // the other endpoint of the new diameter
if (du > diam) {
changed = true;
other = a; // a stays, b becomes i
b = i;
diam = du;
} else if (dv > diam) {
changed = true;
other = b; // b stays, a becomes i
a = i;
diam = dv;
}
// ----- decide what to send -----
int answer = 0; // 0 → no message
if (i >= startIdx) {
if (!initDone) { // first vertex of the suffix
if (changed) {
answer = other + 1; // change already, send it
initDone = true;
} else {
answer = a + 1; // store first endpoint
initDone = true;
pendingSecond = true;
pendingSecondVal = b + 1; // second endpoint to be sent later
}
} else if (pendingSecond) { // we still have to send the second init value
if (changed) {
answer = other + 1; // a real change – we do not need the second init any more
pendingSecond = false;
} else {
answer = pendingSecondVal;
pendingSecond = false;
}
} else { // normal part of the suffix
if (changed) {
answer = other + 1; // a real change
} else {
answer = 0;
}
}
}
return answer; // 0 means “no message”, otherwise 1 … 20000
}
/* ------------------------------------------------------------------ */
std::pair<int,int> longest_path(std::vector<int> S) {
vector<pair<int,int>> msgs; // (index , value)
for (int i = 0; i < (int)S.size(); ++i)
if (S[i] != 0) msgs.emplace_back(i, S[i]);
if (msgs.empty())
return {0,0}; // should never happen
if (msgs.size() == 1) {
return { msgs[0].first , msgs[0].second - 1 };
}
if (msgs.size() == 2) {
int i1 = msgs[0].first, v1 = msgs[0].second;
int i2 = msgs[1].first, v2 = msgs[1].second;
// case: second message is a real change
if (v2 == v1) // init + change (both values equal)
return { i2 , v2 - 1 };
if (v2 - 1 == i1) // change that points to the first vertex
return { i2 , v2 - 1 };
// otherwise two initial messages → the pair of endpoints
return { v1 - 1 , v2 - 1 };
}
// three or more messages → the last one is a real change
return { msgs.back().first , msgs.back().second - 1 };
}
