#include "migrations.h" #include<bits/stdc++.h> using namespace std; vector<int> adj[10001]; vector<int> dist; int p[10001]; pair<int,int> ans = {-1,-1}; int bst = 0; void dfs(int u, int par) { for (auto &v : adj[u]) { if (v == par) continue; dist[v] = dist[u] + 1; dfs(v, u); } } tuple<int,int,int> func(int n) { dist.assign(n, 0); dfs(0, -1); int a = max_element(dist.begin(), dist.end()) - dist.begin(); dist.assign(n, 0); dfs(a, -1); int b = max_element(dist.begin(), dist.end()) - dist.begin(); int d = dist[b]; return {a, b, d}; } int D(int x, int y,int n) { dist.assign(n, 0); dfs(x, -1); return dist[y]; } int send_message(int N, int i, int Pi) { adj[i].emplace_back(Pi); adj[Pi].emplace_back(i); if(i < N-27){ return 0; }else if(i==N-27){ tuple<int,int,int> oc = func(i+1); bst = get<2>(oc); ans = pair<int,int>{get<0>(oc),get<1>(oc)}; int u = ans.first; int v = ans.second; bool A = u & (1<<((N-i-1)/2)); bool B = v & (1<<((N-i-1)/2)); if(A and B){ return 3; }else if(A){ return 1; }else if(B){ return 2; }else return 0; }else{ tuple<int,int,int> oc = func(i+1); int curr = get<2>(oc); pair<int,int> ret = pair<int,int>{get<0>(oc),get<1>(oc)}; int u = ans.first; int v = ans.second; if(curr>bst){ int du = D(u,i,i+1); int dv = D(v,i,i+1); if(du == curr){ bst = curr; ans = pair<int,int>{u,i}; if(i & 1){//if on v return 4; }else{// on u if(u & (1<<((N-i-1)/2))){ return 3; }else return 2; } } else{ bst = curr; ans = pair<int,int>{i,v}; if(i & 1){ if(v & (1<<((N-i-1)/2))){ return 3; }else return 2; }else{ return 4; } } }else{ if(i&1){ if(v & (1<<((N-i-1)/2))){ return 1; }else return 0; }else{ if(u & (1<<((N-i-1)/2))){ return 1; }else return 0; } } } } pair<int, int> longest_path(vector<int> S) { int u = 0; int v = 0; bool cu = false; bool cv = false; int N =S.size(); if(S[N-27] == 3){ u |= (1ll<<13); v |= (1ll<<13); }else if(S[N-26] == 2){ v |= (1ll<<13); }else if(S[N-26] == 1){ u |= (1ll<<13); } for(int i = N-25; i <= N-1; ++i){ if(i & 1){ if(S[i] <= 1){ if(S[i] and !cv){ v |= (1ll<<((N-i-1)/2)); } }else if(S[i] < 4){ if(S[i] == 3 and !cv){ v |= (1ll<<((N-i-1)/2)); } u = i; cu = true; }else{ v = i; cv = true; } }else{ if(S[i] <= 1){ if(S[i] and !cu){ u |= (1ll<<((N-i-1)/2)); } }else if(S[i] < 4){ if(S[i] == 3 and !cu){ u |= (1ll<<((N-i-1)/2)); } v = i; cv = true; }else{ u = i; cu = true; } } } return pair<int,int>{u,v}; }