#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
static const int LOG = 14; // 2^14 > 10000
vector<array<int, LOG>> up;
vector<int> depth_;
pair<int,int> diam_;
int lca(int a, int b) {
if (depth_[a] < depth_[b]) swap(a, b);
int diff = depth_[a] - depth_[b];
for (int j = LOG - 1; j >= 0; --j) {
if (diff & (1 << j)) a = up[a][j];
}
if (a == b) return a;
for (int j = LOG - 1; j >= 0; --j) {
if (up[a][j] != up[b][j]) {
a = up[a][j];
b = up[b][j];
}
}
return up[a][0];
}
int dist_tree(int a, int b) {
int c = lca(a, b);
return depth_[a] + depth_[b] - 2 * depth_[c];
}
int send_message(int N, int i, int Pi) {
if (i == 1) {
up.clear();
depth_.clear();
up.push_back({});
for (int j = 0; j < LOG; ++j) up[0][j] = 0;
depth_.push_back(0);
diam_ = {0, 0};
}
array<int, LOG> cur{};
cur[0] = Pi;
for (int j = 1; j < LOG; ++j) {
cur[j] = up[cur[j - 1]][j - 1];
}
up.push_back(cur);
depth_.push_back(depth_[Pi] + 1);
int oldA = diam_.first;
int oldB = diam_.second;
int oldD = dist_tree(oldA, oldB);
bool changed = false;
int other = -1;
if (dist_tree(i, oldA) > oldD) {
diam_ = {oldA, i};
changed = true;
other = oldA;
} else if (dist_tree(i, oldB) > oldD) {
diam_ = {i, oldB};
changed = true;
other = oldB;
}
int START = max(1, N - 50);
if (i < START) return 0;
if (i == START) {
return diam_.first + 1; // value 1..10000
}
if (i == START + 1) {
if (changed) return 10001 + other; // tagged update
return diam_.second + 1; // second endpoint
}
if (changed) {
return 10001 + other; // tagged update
}
return 0;
}
pair<int,int> longest_path(vector<int> S) {
int N = (int)S.size();
if (N == 1) return {0, 0};
if (N == 2) return {0, 1};
int START = max(1, N - 50);
int A = S[START] - 1;
pair<int,int> ans;
if (S[START + 1] > 10000) {
ans = {START + 1, S[START + 1] - 10001};
} else {
ans = {A, S[START + 1] - 1};
}
for (int i = START + 2; i < N; ++i) {
if (S[i] != 0) {
ans = {i, S[i] - 10001};
}
}
return ans;
}
