#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 400
namespace {
ll opof[MAX]; //onepointofive
vector<ll> adj[303030];
ll ord[303030];
ll num[303030];
ll tnum[303030];
ll cnt = 0;
}
ll dfs(ll x, ll p = -1) {
num[x] = 1;
ord[x] = ++cnt;
ll sum = 0;
for (auto v : adj[x]) {
if (v == p) continue;
ll res = dfs(v, x);
num[x] += res;
sum += res;
cnt = ord[x] + sum;
}
tnum[x] = lower_bound(opof, opof + MAX, num[x]) - opof;
num[x] = opof[tnum[x]];
return num[x];
}
void Encode(int N, int A[], int B[]) {
ll i;
for (i = 1; i < MAX; i++) opof[i] = max(opof[i - 1] + 1, opof[i - 1] * 21 / 20);
for (i = 0; i < N - 1; i++) adj[A[i]].push_back(B[i]), adj[B[i]].push_back(A[i]);
dfs(0);
for (i = 0; i < N; i++) {
Code(i, ord[i] * (MAX) + tnum[i]);
}
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 400
ll opof[MAX];
void InitDevice() {
ll i;
for (i = 1; i < MAX; i++) opof[i] = max(opof[i - 1] + 1, opof[i - 1] * 21 / 20);
}
int Answer(long long S, long long T) {
ll sl, sr, tl, tr;
sl = S / MAX;
tl = T / MAX;
sr = sl + opof[S % MAX];
tr = tl + opof[T % MAX];
if (sl <= tl && tr <= sr) return 1;
else if (tl <= sl && sr <= tr) return 0;
else return 2;
}
