#include "migrations.h"
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
/*
Safe tweaks:
- Reduce the talk window to K=32 (was 50) to lower M without touching correctness.
- Protocol unchanged:
* Maintain online diameter with bounded LCA.
* Speak only in the last K edges.
* At i == startIdx: send A+1
At i == startIdx+1: send B+1
* For any later real diameter change in the suffix: send other+1 at that i.
- Museum:
* startIdx = max(1, N-K)
* If any message exists at i >= startIdx+2, return (i, S[i]-1).
* Else return (S[startIdx]-1, S[startIdx+1]-1).
*/
namespace {
bool inited = false;
int Nglob = 0, LOGv = 0;
int startIdx = 1; // start of last-K window
// LCA tables
vector<int> depth;
vector< vector<int> > up; // up[v][k], k in [0..LOGv-1]
// Online diameter state
int A = 0, B = 0, D = 0;
// Suffix init flags
bool sentInitA = false;
bool sentInitB = false;
inline void reset_test(int N) {
inited = true;
Nglob = N;
LOGv = 0; while ((1 << LOGv) <= (Nglob > 0 ? Nglob : 1)) ++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 = 32 (was 50). Keep at least 1 edge in the suffix if N is tiny.
int K = (Nglob >= 2 ? 32 : max(1, Nglob - 1));
startIdx = max(1, Nglob - K);
sentInitA = false;
sentInitB = false;
}
inline 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 < LOGv; ++k) if (diff & (1 << k)) u = up[u][k];
if (u == v) return u;
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];
}
}
int send_message(int N, int i, int Pi) {
// New test starts at i == 1
if (!inited || i == 1) reset_test(N);
// Build lifting 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 (i == startIdx && !sentInitA) {
out = A + 1; // first init
sentInitA = true;
} else if (i == startIdx + 1 && !sentInitB) {
out = B + 1; // second init
sentInitB = true;
} else if (changed) {
out = other + 1; // real change message
}
// else: silent
}
return out; // 0 means no message; else 1..10000
}
std::pair<int,int> longest_path(std::vector<int> S) {
int N = (int)S.size();
if (N <= 1) return {0, 0};
// Must match K=32 used in send_message
int K = (N >= 2 ? 32 : max(1, N - 1));
int start = max(1, N - K);
// Look for the last message strictly after the two inits
for (int i = N - 1; i >= start + 2; --i) {
if (S[i] != 0) {
return { i, S[i] - 1 };
}
}
// Otherwise fall back to the two deterministic init messages
int u = (S[start] > 0 ? S[start] - 1 : 0);
int v = (S[start + 1] > 0 ? S[start + 1] - 1 : 0);
return { u, v };
}
