#include "Encoder.h" #include <bits/stdc++.h> using namespace std; #define sp << " " << #define emb emplace_back #define MAXN 250000 typedef pair<int,int> ii; const int D=17,SEG=12; int cnt,numNode,dp[2*MAXN+5]; vector<int> g[MAXN+5],gb[2*MAXN+5]; int L[2*MAXN+5],R[2*MAXN+5],num=-1; void initBT(int x,int par){ for(int i=0;i<(int)g[x].size();i++){ if(g[x][i]==par){ g[x].erase(g[x].begin()+i); break; } } int cn=g[x].size(); if(cn>2){ vector<int> bt(2*cn); int l=cn,r=2*cn; for(int i=l;i<r;i++) bt[i]=g[x][i-cn]; l>>=1;r>>=1; while(l>0){ for(int i=r-1;i>=l;i--){ bt[i]=(i>1?cnt++:x); gb[bt[i]].emb(bt[2*i]); gb[bt[i]].emb(bt[2*i+1]); } l>>=1;r>>=1; } } else{ for(auto i:g[x]) gb[x].emb(i); } for(auto i:g[x]) initBT(i,x); } void dfs(int x){ dp[x]=1; for(auto i:gb[x]){ dfs(i); dp[x]=max(dp[x],dp[i]+1); } } void leaf(int x,int group,int p){ if(x>=numNode) return; //~ cout << ":" sp x sp group sp p << "\n"; long long code=p+((long long)group<<D); code=code<<1|1; Code(x,code); } void node(int x,int h){ if(x>=numNode) return; //~ cout << ":" sp x sp L[x] sp R[x] sp h << "\n"; long long code=R[x]+((long long)L[x]<<SEG)+((long long)h<<(2*SEG)); code=code<<1; Code(x,code); } void calc(int x,int h,bool lf){ if(lf){ leaf(x,num,h); int t=0; for(auto i:gb[x]){ calc(i,h<<1|t,1); t^=1; } } else{ if(dp[x]<=D){ L[x]=R[x]=++num;h=1; leaf(x,num,h); int t=0; for(auto i:gb[x]){ calc(i,h<<1|t,1); t^=1; } } else{ L[x]=cnt;R[x]=0; for(auto i:gb[x]){ if(gb[x].size()==1) calc(i,h+1,0); else calc(i,0,0); L[x]=min(L[x],L[i]); R[x]=max(R[x],R[i]); } node(x,h); } } } void Encode(int N, int A[], int B[]) { for(int i=0;i<N-1;i++){ g[A[i]].emb(B[i]); g[B[i]].emb(A[i]); } cnt=numNode=N; initBT(0,-1); //~ for(int i=0;i<cnt;i++){ //~ cout << i << ": "; //~ for(auto j:gb[i]) //~ cout << j << " "; //~ cout << "\n"; //~ } dfs(0); calc(0,0,0); }

#include "Device.h" #include <bits/stdc++.h> #define sp << " " << using namespace std; const int d=17,seg=12; void InitDevice(){} int Answer(long long S, long long T){ if((S&1) && (T&1)){ S>>=1;T>>=1; int path1=S%(1<<d); int k1=S>>d; int path2=T%(1<<d); int k2=T>>d;; //~ cout << k1 sp path1 sp k2 sp path2 << "\n"; if(k1==k2){ auto ff=[](int x){ int ans=0; while(x) x>>=1,ans++; return ans; }; int len1=ff(path1); int len2=ff(path2); if(len1>len2) swap(path1,path2); for(int i=abs(len2-len1);i;i--) path2>>=1; if(path1==path2) return (len1<len2?1:0); return 2; } return 2; } else if(!(S&1) && (T&1)){ S>>=1;T>>=1; int r=S%(1<<seg); int l=(S>>seg)%(1<<seg); int k=T>>d; if(l<=k && k<=r) return 1; return 2; } else if((S&1) && !(T&1)){ S>>=1;T>>=1; int r=T%(1<<seg); int l=(T>>seg)%(1<<seg); int k=S>>d; if(l<=k && k<=r) return 0; return 2; } else{ S>>=1;T>>=1; int r1=S%(1<<seg); int l1=(S>>seg)%(1<<seg); int h1=S>>(2*seg); int r2=T%(1<<seg); int l2=(T>>seg)%(1<<seg); int h2=T>>(2*seg); if(r1<l2 || r2<l1) return 2; if(l1==l2 && r1==r2) return (h1<h2?1:0); else{ int len1=r1-l1,len2=r2-l2; return (len1>len2?1:0); } } }