#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const double R = 1.054;
const int maxn = 2.5e5 + 5;
int tym = 0;
vector<int> lg, g[maxn];
int length(int x) {
return *lower_bound(lg.begin(), lg.end(), x); }
int Log(int x) {
return lower_bound(lg.begin(), lg.end(), x) - lg.begin(); }
void dfs(int u, int p) {
int L = tym++;
for(int v : g[u]) if(v != p) {
dfs(v, u);
}
tym = L + length(tym - L);
Code(u, L << 8 | Log(tym - L));
}
void Encode(int N, int A[], int B[]) {
{
lg.clear();
double p = 1;
while(p < 1000000000.0) {
lg.emplace_back(floor(p));
p *= R;
}
sort(lg.begin(), lg.end());
lg.erase(unique(lg.begin(), lg.end()), lg.end());
}
for(int i = 0; i < N - 1; i++) {
int u = A[i], v = B[i];
g[u].emplace_back(v);
g[v].emplace_back(u);
} dfs(0, -1);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
#define lg antilog
const double R = 1.054;
const int maxn = 2.5e5 + 5;
vector<int> lg;
void InitDevice() {
double p = 1;
while(p < 1000000000.0) {
lg.emplace_back(floor(p));
p *= R;
}
sort(lg.begin(), lg.end());
lg.erase(unique(lg.begin(), lg.end()), lg.end());
}
pair<int, int> decode(long long code) {
return {code >> 8, (code >> 8) + lg[code & ((1 << 8) - 1)] - 1};
}
int Answer(long long u, long long v) {
int ul, ur, vl, vr;
tie(ul, ur) = decode(u);
tie(vl, vr) = decode(v);
if(vl <= ul and ur <= vr) return 0;
if(ul <= vl and vr <= ur) return 1;
return 2;
}
