#include "telepathy.h" using namespace std; #include <iostream> const int log = 8; vector<int> bruma(int N, vector<int> A, vector<int> B, int S, int turn) { vector<vector<int>> ad(N); for(int i=0; i<N-1; i++) { ad[A[i]].push_back(B[i]); ad[B[i]].push_back(A[i]); } pair<int, int> centroid = {-1, -1}; vector<int> sz(N); vector<int> up(N); auto dfs = [&](auto &&self, int v, int p) -> void { up[v] = p; sz[v] = 1; for(int u: ad[v]) { if(u == p) continue; self(self, u, v); sz[v] += sz[u]; } }; auto find_centroid = [&](auto &&self, int v, int p) -> void { int sz_sum = 1; bool is_centroid = 1; for(int u: ad[v]) { if(u == p) continue; self(self, u, v); sz_sum += sz[u]; if(sz[u] > N/2) is_centroid = 0; } if(N - sz_sum > N/2) is_centroid = 0; if(is_centroid) { centroid.second = v; if(centroid.first == -1) centroid.first = v; } }; dfs(dfs, 0, 0); find_centroid(find_centroid, 0, 0); dfs(dfs, centroid.first, centroid.second); dfs(dfs, centroid.second, centroid.first); vector<int> ans; int curr_node = S; ans.push_back(curr_node); for(int i=0; i<=log; i++) { for(int j=0; j<(1 << i); j++) { if(turn) curr_node = up[curr_node]; ans.push_back(curr_node); if(ans.size() == 10*N + 1) return ans; } turn ^= 1; } while(ans.size() < 10*N + 1) ans.push_back(ans.back()); return ans; } vector<int> Aitana(int N, vector<int> A, vector<int> B, int S, int subtask) { return bruma(N, A, B, S, 0); } vector<int> Bruno(int N, vector<int> C, vector<int> D, int T, int subtask) { return bruma(N, C, D, T, 1); }