#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
/*
Robust, low-chatter, unambiguous protocol.
—we maintain the current diameter (A,B) online with LCA.
—we only transmit in the last K=50 insertions: startIdx = max(1, N-K).
—on a REAL diameter change at i, we send EVEN = (other_endpoint + 1) forced even.
—otherwise (no change), we send exactly TWO ODD inits once in the suffix:
1) (A + 1) forced odd
2) (B + 1) forced odd (skipped if a change happens before sending it)
Museum decoding:
—if any EVEN message exists, take the LAST EVEN → (U = that i, V = value-1).
—else take the LAST TWO ODD messages → (U = odd1-1, V = odd2-1).
Key fix vs. previous attempts: LCA lifting loops are BOUNDED by LOGv.
*/
namespace {
// per-test state
bool inited = false;
int Nglob = 0, LOGv = 0;
int K = 50, startIdx = 1;
vector<int> depth;
vector<vector<int>> up; // up[v][k], k in [0..LOGv-1]
int A = 0, B = 0, D = 0; // current diameter endpoints and length
bool sentInit1 = false, sentInit2Pending = false;
int init2Val = 0;
inline void reset_test(int N){
inited = true;
Nglob = N;
LOGv = 0; while ((1 << LOGv) <= max(1, Nglob)) ++LOGv;
depth.assign(Nglob, 0);
up.assign(Nglob, vector<int>(LOGv, 0));
for (int k = 0; k < LOGv; ++k) up[0][k] = 0;
A = B = 0; D = 0;
K = min(50, max(1, Nglob - 1));
startIdx = max(1, Nglob - K);
sentInit1 = false;
sentInit2Pending = false;
init2Val = 0;
}
inline int lca(int u, int v){
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
// lift u by bounded bits of diff
for (int k = 0; k < LOGv; ++k){
if (diff & (1 << k)) u = up[u][k];
}
if (u == v) return u;
// jump both up
for (int k = LOGv - 1; k >= 0; --k){
if (up[u][k] != up[v][k]){
u = up[u][k];
v = up[v][k];
}
}
return up[u][0];
}
inline int dist(int u, int v){
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}
inline int force_even(int x){ return (x & 1) ? x + 1 : x; }
inline int force_odd (int x){ return (x & 1) ? x : x + 1; }
}
int send_message(int N, int i, int Pi){
// Reinit per test when i==1 (new test case)
if (!inited || i == 1) reset_test(N);
// Fill lifting info for node i
depth[i] = depth[Pi] + 1;
up[i][0] = Pi;
for (int k = 1; k < LOGv; ++k) up[i][k] = up[ up[i][k-1] ][k-1];
// Online diameter update
int dA = dist(i, A);
int dB = dist(i, B);
bool changed = false;
int other = -1;
if (dA > D){ changed = true; other = A; B = i; D = dA; }
else if (dB > D){ changed = true; other = B; A = i; D = dB; }
int out = 0;
if (i >= startIdx){
if (changed){
// Real change → EVEN-coded other+1
int v = other + 1; // 1..N ≤ 10000
v = force_even(v); // make it even to mark "change"
// v ≤ 10000, so ≤ 20000 bound always satisfied
out = v;
// once a real change occurs, we skip pending init2
sentInit2Pending = false;
} else if (!sentInit1){
// First init → ODD-coded A+1
int v = force_odd(A + 1);
out = v;
sentInit1 = true;
sentInit2Pending = true;
init2Val = force_odd(B + 1);
} else if (sentInit2Pending){
// Second init → ODD-coded B+1
out = init2Val;
sentInit2Pending = false;
}
// else: stay silent
}
return out; // 0 = no message
}
std::pair<int,int> longest_path(std::vector<int> S){
// Collect nonzero messages
vector<pair<int,int>> msgs;
msgs.reserve(S.size());
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}; // degenerate tiny trees
// Prefer the last EVEN message → final real change
for (int t = (int)msgs.size() - 1; t >= 0; --t){
if ((msgs[t].second & 1) == 0){
int idx = msgs[t].first;
int v = msgs[t].second - 1; // decode other endpoint
return { idx, v };
}
}
// Otherwise, use the last two ODD messages (the two init endpoints)
int found = 0;
int v_last = -1, v_prev = -1;
for (int t = (int)msgs.size() - 1; t >= 0 && found < 2; --t){
if ((msgs[t].second & 1) == 1){
if (found == 0) v_last = msgs[t].second - 1;
else v_prev = msgs[t].second - 1;
++found;
}
}
if (found == 2) return { v_prev, v_last };
// Fallback: single odd message — interpret as (idx, val-1)
auto [idx, val] = msgs.back();
return { idx, val - 1 };
}
