// 5.99d turns solution for general cases
#include "telepathy.h"
#include <algorithm>
#include <iostream>
// make adjacency list
std::vector<std::vector<int> > make_graph(int N, const std::vector<int>& A, const std::vector<int>& B) {
std::vector<std::vector<int> > G(N);
for (int i = 0; i < N - 1; i++) {
G[A[i]].push_back(B[i]);
G[B[i]].push_back(A[i]);
}
return G;
}
// find centroid of tree
std::vector<int> find_centroid(int N, const std::vector<std::vector<int> >& G) {
std::vector<int> res;
std::vector<int> subsize(N, 1);
auto dfs = [&](auto& self, int x, int pre) -> void {
bool ok = true;
for (int i : G[x]) {
if (i != pre) {
self(self, i, x);
subsize[x] += subsize[i];
if (subsize[i] * 2 > N) {
ok = false;
}
}
}
if (ok && subsize[x] * 2 >= N) {
res.push_back(x);
}
};
dfs(dfs, 0, -1);
return res;
}
// find S-T path on tree
std::vector<int> find_path(int N, std::vector<std::vector<int> > G, int S, int T) {
std::vector<int> par(N, -1);
auto dfs = [&](auto& self, int x, int pre) -> void {
par[x] = pre;
for (int i : G[x]) {
if (i != pre) {
self(self, i, x);
}
}
};
dfs(dfs, T, -1);
std::vector<int> seq = {S};
while (seq.back() != T) {
seq.push_back(par[seq.back()]);
}
return seq;
}
// sequence of changes of (depth of A) - (depth of B)
std::vector<int> instruction(int N, int player) {
double mul = 1.0;
std::vector<int> seq;
int turn = 0, l = 0, r = 0;
while (int(seq.size()) < 10 * N) {
if (turn == 0) {
int nr = int(mul);
int pre = l;
for (int i = l + 1; i <= r; i++) {
if ((i & 1) == 0) {
seq.push_back(i - pre);
pre = i;
}
}
seq.push_back((r + 1) - pre);
for (int i = r + 2; i <= nr; i++) {
seq.push_back(+1);
}
r = nr;
} else {
int nl = -int(mul);
int pre = r;
for (int i = r - 1; i >= l; i--) {
if ((i & 1) == 1) {
seq.push_back(i - pre);
pre = i;
}
}
seq.push_back((l - 1) - pre);
for (int i = l - 2; i >= nl; i--) {
seq.push_back(-1);
}
l = nl;
}
turn ^= 1;
mul *= 1.685;
}
seq.resize(10 * N);
std::vector<int> res(10 * N);
for (int i = 0; i < 10 * N; i++) {
if (player == 0) {
res[i] = (seq[i] >= +1 ? +1 : seq[i] == -2 ? -1 : 0);
} else {
res[i] = (seq[i] <= -1 ? +1 : seq[i] == +2 ? -1 : 0);
}
}
return res;
}
// Aitana's strategy
std::vector<int> Aitana(int N, std::vector<int> A, std::vector<int> B, int S, int subtask) {
std::vector<std::vector<int> > G = make_graph(N, A, B);
std::vector<int> centroids = find_centroid(N, G);
std::vector<int> path;
for (int i : centroids) {
std::vector<int> subpath = find_path(N, G, S, i);
if (path.empty() || path.size() > subpath.size()) {
path = subpath;
}
}
std::vector<int> seq = instruction(N, 0);
std::vector<int> res(10 * N + 1, -1);
res[0] = S;
int pos = 0;
for (int i = 0; i < 10 * N; i++) {
pos += seq[i];
res[i + 1] = path[std::max(std::min(pos, int(path.size()) - 1), 0)];
}
return res;
}
// Bruno's strategy
std::vector<int> Bruno(int N, std::vector<int> C, std::vector<int> D, int T, int subtask) {
std::vector<std::vector<int> > G = make_graph(N, C, D);
std::vector<int> centroids = find_centroid(N, G);
std::vector<int> path;
for (int i : centroids) {
std::vector<int> subpath = find_path(N, G, T, i);
if (path.empty() || path.size() > subpath.size()) {
path = subpath;
}
}
std::vector<int> seq = instruction(N, 1);
std::vector<int> res(10 * N + 1, -1);
res[0] = T;
int pos = 0;
for (int i = 0; i < 10 * N; i++) {
pos += seq[i];
res[i + 1] = path[std::max(std::min(pos, int(path.size()) - 1), 0)];
}
for (int i = 1; i <= 10 * N; i++) {
if (centroids.size() == 2 && res[i - 1] == path.back() && (i == 10 * N || res[i + 1] == path.back())) {
res[i] = centroids[0] + centroids[1] - path.back();
}
}
return res;
}
