#include <vector>
#include <algorithm>
#include <utility>
namespace {
// ----- global data kept only during the first run -------------
std::vector<int> _depth;
std::vector<std::vector<int>> _up;
int _LOG = 0;
int _a = 0, _b = 0, _diam = 0;
int _N = 0;
int _suffix_start = 0;
const int _suffix_len = 28;
// ----- auxiliary tree functions --------------------------------
int _lca(int u, int v) {
if (_depth[u] < _depth[v]) {
std::swap(u, v);
}
// lift u to depth of v
int diff = _depth[u] - _depth[v];
int bit = 0;
while (diff > 0) {
if (diff & 1) {
u = _up[u][bit];
}
diff >>= 1;
bit++;
}
if (u == v) {
return u;
}
// lift both while ancestors differ
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]; // parent of u (or v)
}
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) {
// ----- first call : initialise -----
// Assuming the function is called for i = 1 .. N-1 in increasing order
if (i == 1) {
_N = N;
// Calculate bit_length() + 1
int temp = N;
int bit_length = 0;
while (temp > 0) {
temp >>= 1;
bit_length++;
}
_LOG = bit_length + 1;
_depth.assign(N, 0);
_up.assign(N, std::vector<int>(_LOG, -1));
_a = 0;
_b = 0;
_diam = 0;
// suffix of length 28 (if the tree is larger)
if (N > _suffix_len) {
_suffix_start = N - _suffix_len;
} else {
_suffix_start = 0;
}
}
// ----- insert vertex i -----
int p = Pi;
_depth[i] = _depth[p] + 1;
_up[i][0] = p;
for (int k = 1; k < _LOG; k++) {
int anc = _up[i][k - 1];
_up[i][k] = (anc != -1) ? _up[anc][k - 1] : -1;
}
// ----- possibly enlarge the diameter -----
int d1 = _dist(i, _a);
if (d1 > _diam) {
_b = i;
_diam = d1;
} else {
int d2 = _dist(i, _b);
if (d2 > _diam) {
_a = i;
_diam = d2;
}
}
// ----- small N : encode everything in the last vertex -----
if (_N <= _suffix_len) {
if (i == _N - 1) {
// encode (a , b) as a*(N+1) + b + 1
return _a * (_N + 1) + _b + 1;
}
return 0;
}
// ----- large N : use the suffix -----
if (i < _suffix_start) {
return 0; // before the communication suffix
}
int offset = i - _suffix_start; // 0 ... 27
bool region_a = (offset < 14); // a-bits part?
bool region_b = !region_a;
bool a_inside = (_a >= _suffix_start);
bool b_inside = (_b >= _suffix_start);
// marker for a ?
if (a_inside && i == _a) {
if (region_a) {
return 2;
} else {
int b_bit = (_b < _suffix_start) ? ((_b >> (offset - 14)) & 1) : 0;
return b_bit ? 3 : 2;
}
}
// marker for b ?
if (b_inside && i == _b) {
if (region_b) {
return 4;
} else {
int a_bit = (_a < _suffix_start) ? ((_a >> offset) & 1) : 0;
return a_bit ? 5 : 4;
}
}
// ordinary bit
if (region_a) {
if (_a < _suffix_start && ((_a >> offset) & 1)) {
return 1;
}
return 0;
} else {
if (_b < _suffix_start && ((_b >> (offset - 14)) & 1)) {
return 1;
}
return 0;
}
}
// ------------------------------------------------------------
std::pair<int, int> longest_path(std::vector<int> S) {
int N = S.size();
// trivial tree of one vertex
if (N == 1) {
return {0, 0};
}
// small N - the answer was packed into a single number
if (N <= 28) { // using literal instead of _suffix_len to keep it stateless
int base = N + 1;
int code = S[N - 1] - 1;
int a = code / base;
int b = code % base;
return {a, b};
}
int suffix_start = N - 28;
int a = -1; // -1 represents Python's None
int b = -1;
int bits_a = 0;
int bits_b = 0;
for (int offset = 0; offset < 28; offset++) {
int i = suffix_start + offset;
if (i >= N) {
break;
}
int val = S[i];
if (val == 0) {
continue;
}
bool region_a = (offset < 14);
bool region_b = !region_a;
// ordinary bits
if (val == 1) {
if (region_a) {
bits_a |= (1 << offset);
} else {
bits_b |= (1 << (offset - 14));
}
continue;
}
// markers for a
if (val == 2 || val == 3) {
a = i;
if (region_b) { // a inside b-part -> b-bit is encoded
if (val == 3) { // b-bit = 1
bits_b |= (1 << (offset - 14));
}
}
continue;
}
// markers for b
if (val == 4 || val == 5) {
b = i;
if (region_a) { // b inside a-part -> a-bit is encoded
if (val == 5) { // a-bit = 1
bits_a |= (1 << offset);
}
}
continue;
}
}
if (a == -1) {
a = bits_a;
}
if (b == -1) {
b = bits_b;
}
return {a, b};
}
