#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
int lch[500005];
int rch[500005];
int curnodes,n;
vector<int> adjl[250005];
double const1 = 0.0;
double const2 = 1.0;
const int cutoffval = 22;
double func(int node, int pa){
set<pair<double,int> > stuff;
for (auto x : adjl[node]){
if (x==pa) continue;
double res = func(x,node);
stuff.insert({res,x});
}
while (stuff.size()>2){
auto i1 = *stuff.begin();
stuff.erase(stuff.begin());
pair<double,int> thing = {-999.0,-1};
auto it = stuff.lower_bound({i1.first+const1,-1});
if (it!=stuff.end()){
thing = (*it);
}
if (it!=stuff.begin()){
it--;
if (abs(thing.first-(i1.first+const1))>=abs((*it).first-(i1.first+const1))){
thing = *it;
}
}
auto i2 = thing;
stuff.erase(stuff.lower_bound(thing));
int nw = curnodes++;
lch[nw] = i2.second;
rch[nw] = i1.second;
stuff.insert({max(i2.first+const2,i1.first+const1+const2),nw});
}
if (stuff.size()==2){
auto i1 = *stuff.begin();
stuff.erase(stuff.begin());
auto i2 = *stuff.begin();
stuff.erase(stuff.begin());
lch[node] = i2.second;
rch[node] = i1.second;
return max(i2.first+const2,i1.first+const1+const2);
}
if (stuff.size()==1){
auto i1 = *stuff.begin();
lch[node] = i1.second;
return i1.first+const2;
}
return 0.0;
}
void dfs2(int node, long long curamt, int pos, int h){
//printf("ch of %d = %d %d\n",node,lch[node],rch[node]);
//printf("pos = %d\n",pos);
if (node<n){
// printf("code %d %lld\n",node,curamt+(1LL<<pos));
Code(node,curamt+(1LL<<pos));
}
if (h>=cutoffval){
if (lch[node]!=-1){
dfs2(lch[node],curamt,pos+1,h+1);
}
if (rch[node]!=-1){
dfs2(rch[node],curamt+(1LL<<pos),pos+1,h+1);
}
return;
}
if (lch[node]!=-1){
if (lch[node]<n) Code(lch[node],curamt+(5LL<<pos));
if (lch[lch[node]]!=-1){
dfs2(lch[lch[node]],curamt,pos+1,h+2);
}
if (rch[lch[node]]!=-1){
dfs2(rch[lch[node]],curamt+(1LL<<pos),pos+3,h+2);
}
}
if (rch[node]!=-1){
if (rch[node]<n) Code(rch[node],curamt+(7LL<<pos));
if (lch[rch[node]]!=-1){
dfs2(lch[rch[node]],curamt+(3LL<<pos),pos+3,h+2);
}
if (rch[rch[node]]!=-1){
dfs2(rch[rch[node]],curamt+(7LL<<pos),pos+3,h+2);
}
}
}
void Encode(int N, int A[], int B[])
{
n = N;
memset(lch,-1,sizeof(lch));
memset(rch,-1,sizeof(rch));
curnodes = N;
for (int x = 0; x<N-1; x++){
adjl[A[x]].push_back(B[x]);
adjl[B[x]].push_back(A[x]);
}
func(0,-1);
dfs2(0,0,0,0);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
const int cutoffval = 22;
void InitDevice()
{
}
int Answer(long long S, long long T)
{
string s1,s2;
for (int x = 0; x<64; x++){
if (S)s1.push_back((S&1)?'1':'0');
S>>=1;
if (T)s2.push_back((T&1)?'1':'0');
T>>=1;
}
s1.pop_back();
s2.pop_back();
int h = 0;
for (int x = 0; x<min(s1.size(),s2.size());){
if (h>=cutoffval){
if (s1[x]!=s2[x]) return 2;
x++;
continue;
}
if (s1[x]=='0'){
if (s2[x]=='0') {
x++; h+=2; continue;
}
if (s2[x+1]=='0'){
if (s2.size()==x+2){
return 0;
}
}
return 2;
}
else if (s2[x]=='0'){
if (s1[x+1]=='0'){
if (s1.size()==x+2){
return 1;
}
}
return 2;
}
else if (min(s1.size(),s2.size())==x+2){
if (s1[x]==s2[x] && s1[x+1]==s2[x+1]) {
x+=2;
h += 1;
continue;
}
else{
return 2;
}
}
else{
if (s1[x]==s2[x] && s1[x+1]==s2[x+1] && s1[x+2]==s2[x+2]){
x+=3;
h+=2;
continue;
}
return 2;
}
}
//printf("cmp %s %s\n",s1.c_str(),s2.c_str());
return s1.size()<s2.size()?1:0;
if (s1.size()<s2.size()){
for (int x = 0; x<s1.size(); x++){
if (s1[x]!=s2[x]) return 2;
}
return 1;
}
for (int x = 0; x<s2.size(); x++){
if (s1[x]!=s2[x]) return 2;
}
return 0;
}
