#include "Encoder.h"
#include <bits/stdc++.h>
#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif
using namespace std;
typedef long long ll;
static vector<int> adj[250010];
static int seen[250010];
static int sz[250010];
int findsz(int a)
{
if (sz[a]) return sz[a];
sz[a] = 1;
for (auto b : adj[a])
{
if (sz[b]) continue;
sz[a] += findsz(b);
}
return sz[a];
}
void dfs(int a, ll node);
void dothing(int a, ll node, vector<pair<int, int> >& children)
{
if (children.empty()) return;
int sum = accumulate(children.begin(), children.end(), 0, [](const int &a, const pair<int, int> &b) { return a+b.first;});
int am = 0;
vector<pair<int, int> > after;
for (int i = children.size()-1; i >= 0; i--)
{
after.push_back(children[i]);
am += children[i].first;
// D("%d: here %d, %d, sum %d\n", a, am, i, sum);
children.pop_back();
if (am >= sum/2)
{
reverse(after.begin(), after.end());
assert(children.size());
if (children.size() == 1)
{
dfs(children[0].second, 2*node);
}
else dothing(a, 2*node, children);
if (after.size() == 1) dfs(after[0].second, 2*node+1);
else dothing(a, 2*node+1, after);
return;
}
}
}
void dfs(int a, ll node)
{
vector<pair<int, int> > children;
seen[a] = 1;
Code(a, node);
D("%d: %lld\n", a, node);
for (auto b : adj[a])
{
if (seen[b]) continue;
children.push_back({sz[b], b});
}
sort(children.begin(), children.end());
if (children.size() == 1) dfs(children[0].second, 2*node);
else dothing(a, node, children);
}
void Encode(int n, int a[], int b[])
{
for (int i = 0; i < n-1; i++)
{
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
findsz(0);
dfs(0, 1);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void InitDevice()
{
}
ll LOG2(ll a)
{
int ans = 0;
while (a)
{
ans++;
a/=2;
}
return ans;
}
int Answer(ll s, ll t)
{
int hei1 = LOG2(s);
int hei2 = LOG2(t);
int sbigger = hei1 < hei2;
while (hei1 > hei2) hei1--, s/=2;
while (hei1 < hei2) hei2--, t/=2;
if (s == t) return sbigger;
else return 2;
}
