#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
static const int LOG = 15; // 2^14 = 16384 > 10000
static int N_global = -1; // set on first call
static vector<int> parent_arr; // parent[i]
static vector<int> depth_arr; // depth[i]
static vector<array<int, LOG>> up; // binary lifting table
static int endA = 0, endB = 0; // current diameter endpoints
static int diam = 0; // current diameter length
/*---------------------------------------------------------------*/
/* lowest common ancestor (binary lifting) */
static int lca(int u, int v) {
if (depth_arr[u] < depth_arr[v]) swap(u, v);
int diff = depth_arr[u] - depth_arr[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];
}
/*---------------------------------------------------------------*/
static inline int dist(int u, int v) {
int w = lca(u, v);
return depth_arr[u] + depth_arr[v] - 2 * depth_arr[w];
}
/*---------------------------------------------------------------*/
int send_message(int N, int i, int Pi) {
/* first call – initialise all structures */
if (N_global != N) {
N_global = N;
parent_arr.assign(N, 0);
depth_arr.assign(N, 0);
up.assign(N, {});
// root 0
parent_arr[0] = 0;
depth_arr[0] = 0;
for (int k = 0; k < LOG; ++k) up[0][k] = 0;
endA = endB = 0;
diam = 0;
}
/* store the new vertex */
parent_arr[i] = Pi;
depth_arr[i] = depth_arr[Pi] + 1;
up[i][0] = Pi;
for (int k = 1; k < LOG; ++k)
up[i][k] = up[ up[i][k - 1] ][k - 1];
/* update the diameter */
int d1 = dist(i, endA);
if (d1 > diam) {
diam = d1;
endB = i; // new diameter (i , endA)
} else {
int d2 = dist(i, endB);
if (d2 > diam) {
diam = d2;
endA = i; // new diameter (i , endB)
}
}
/* we do not send any message */
return 0;
}
/*---------------------------------------------------------------*/
std::pair<int,int> longest_path(std::vector<int> /*S*/) {
// the answer has already been computed while processing the tree
return {endA, endB};
}
