#include "migrations.h" #include <bits/stdc++.h> using namespace std; namespace { vector<vector<int>> adj; pair<int,int> dfs(int x,int p){ pair<int,int> ans = {-1,x}; for(int&i:adj[x])if(i!=p){ ans = max(ans,dfs(i,x)); } ans.first++; return ans; } int currL,currR,currBest; } int send_message(int N, int i, int Pi) { if(i==1)adj.resize(N); adj[i].emplace_back(Pi); adj[Pi].emplace_back(i); if(i==9978){ currL = dfs(0,-1).second; currR = dfs(currL,-1).second; currBest = dfs(currL,-1).first; return 0; } if(i>9978 and i<9986){ // sending L phase if(dfs(currR,-1).first!=currBest){ // replacing L currL = i; currBest++; return 0; } if(dfs(currL,-1).first!=currBest){ currR = i; currBest++; } int bits = (i-9978-1)*2; return ((currL>>bits)&3)+1; } if(i>9985){ // sending R phase int offset = 0; if(dfs(currR,-1).first!=currBest){ // replacing L currL = i; currBest++; offset = 2; } if(dfs(currL,-1).first!=currBest){ currR = i; currBest++; return 0; } int bits = (i-9985-1); return (((currR>>bits)&1) + offset)+1; } return 0; } pair<int,int> longest_path(vector<int> S){ int currL = 0; int currR = 0; for(int i=9979;i<9986;i++){ // reading currL if(S[i]==0)currL=i; else { int c = S[i]-1; int bits = (i-9978-1)*2; currL|=c<<bits; } } for(int i=9986;i<10000;i++){ // reading currR if(S[i]==0)currR=i; else { int c = S[i]-1; if(c&2){ currL = i; c&=1; } int bits = (i-9985-1); currR|=c<<bits; } } return {currL,currR}; }