#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
/*
Protocol (suffix-only, K=50):
- While visiting the last K nodes (i >= N-K):
* If adding node i changes the current diameter (u,v) to include i, send
S[i] = other_endpoint + 1 // 1..10000 (UNTAGGED)
* Else, if we have not yet sent the two "init" messages, send:
first init: S[i] = 10000 + (a + 1) // 10001..20000 (TAGGED)
second init: S[i] = 10000 + (b + 1) // 10001..20000 (TAGGED)
(We skip the second init if a real change occurs before we send it.)
- Outside the suffix: send 0.
Decoding:
- If there exists at least one UNTAGGED message (<=10000), take the last one:
answer = (last_index, S[last_index] - 1)
- Else, take the last two TAGGED messages (>10000):
answer = ( (S1-10000)-1 , (S2-10000)-1 )
This is unambiguous and within bounds.
*/
namespace {
// Per-test static state
bool inited = false;
int Nglob = 0, LOG = 0, K = 50, startIdx = 1;
// Tree state
vector<int> depth;
vector<array<int, 20>> up; // 20 > ceil(log2(10000))=14; keep slack
// Current diameter endpoints and length
int A = 0, B = 0, D = 0;
// Suffix init bookkeeping
bool sentInit1 = false, sentInit2Pending = false;
int init2Val = 0;
// Lift / LCA helpers
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; diff; ++k, diff >>= 1) if (diff & 1) 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];
}
inline int dist(int u, int v) {
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}
inline void reset_test(int N) {
inited = true;
Nglob = N;
LOG = 0; while ((1 << LOG) <= max(1, Nglob)) ++LOG;
depth.assign(Nglob, 0);
up.assign(Nglob, {});
for (int k = 0; k < LOG; ++k) up[0][k] = 0;
A = B = 0; D = 0;
K = min(50, max(1, Nglob - 1)); // talk in the last up to 50 edges
startIdx = max(1, Nglob - K);
sentInit1 = false;
sentInit2Pending = false;
init2Val = 0;
}
}
int send_message(int N, int i, int Pi) {
// Per-test reinitialization when a new test case starts (first edge i==1)
if (!inited || i == 1) {
reset_test(N);
}
// Build lifting info for node 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];
// Check if adding i changes current diameter
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;
}
// Default: no message
int out = 0;
const int TAG_BASE = 10000; // tag threshold
if (i >= startIdx) {
if (changed) {
// Real change: send untagged other+1 (<= 10000)
out = other + 1;
// Any pending second init becomes unnecessary/ambiguous → cancel it
sentInit2Pending = false;
} else if (!sentInit1) {
// First time we speak in the suffix, and no change yet: send tagged A
out = TAG_BASE + (A + 1);
sentInit1 = true;
sentInit2Pending = true;
init2Val = TAG_BASE + (B + 1);
} else if (sentInit2Pending) {
// Send the second tagged init, unless a change already happened (handled above)
out = init2Val;
sentInit2Pending = false;
} // else remain silent
}
// Sanity: keep within bounds (debug guard; not needed in grader)
// if (out < 0 || out > 20000) out = 0;
return out;
}
std::pair<int,int> longest_path(std::vector<int> S) {
// Gather all messages (index, value)
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 there is any UNTAGGED change message (<=10000), the last one encodes (i, other)
int lastChangeIdx = -1, lastChangeVal = -1;
for (int t = (int)msgs.size() - 1; t >= 0; --t) {
if (msgs[t].second <= 10000) { lastChangeIdx = msgs[t].first; lastChangeVal = msgs[t].second; break; }
}
if (lastChangeIdx != -1) {
return { lastChangeIdx, lastChangeVal - 1 };
}
// Otherwise, we must have sent two TAGGED inits (>10000). Use the last two.
int tagged1 = -1, tagged2 = -1; // last then previous
for (int t = (int)msgs.size() - 1; t >= 0; --t) {
if (msgs[t].second > 10000) {
if (tagged1 == -1) tagged1 = msgs[t].second;
else { tagged2 = msgs[t].second; break; }
}
}
if (tagged1 != -1 && tagged2 != -1) {
int u = (tagged2 - 10000) - 1;
int v = (tagged1 - 10000) - 1;
return {u, v};
}
// Extremely degenerate edge cases (shouldn't occur with N=10000/K>=2), fallback:
if (!msgs.empty()) {
int i = msgs.back().first, v = msgs.back().second;
if (v <= 10000) return { i, v - 1 };
int u = (v - 10000) - 1;
// Pair with something plausible; this path should never trigger on official tests.
return { 0, max(0, u) };
}
return {0, 0};
}
