#include "Encoder.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; namespace { set<int> pos_len; map<int,int> mp; map<int,int> mp2; vi graph[250001]; int pre[250001]; int len[250001]; int cur_pre = 0; const int k = 1000000; void init() { ld x = 1; while(x < k) { pos_len.insert((ll)x); x *= 1.05; } pos_len.insert(k); int cur = 0; forall(it,pos_len) { mp[it] = cur; mp2[cur++] = it; } } void dfs(int v, int pop) { pre[v] = cur_pre++; forall(it,graph[v]) { if(it != pop) dfs(it,v); } auto p = pos_len.lower_bound(cur_pre-pre[v]); len[v] = *p; cur_pre = pre[v]+*p; } } void Encode(int n, int A[], int B[]) { rep(i,n) graph[i] = {}; rep(i,n-1) { graph[A[i]].pb(B[i]); graph[B[i]].pb(A[i]); } cur_pre = 0; init(); dfs(0,0); rep(i,n) { Code(i,mp[len[i]]+siz(pos_len)*pre[i]); } }

#include "Device.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; //mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} //ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; namespace { set<int> pos_len; map<int,int> mp; map<int,int> mp2; const int k = 1000000; void init() { ld x = 1; while(x < k) { pos_len.insert((ll)x); x *= 1.05; } pos_len.insert(k); int cur = 0; forall(it,pos_len) { mp[it] = cur; mp2[cur++] = it; } } } void InitDevice() { init(); } int Answer(ll S, ll T) { int len_S = mp2[S%siz(pos_len)]; int pre_S = S/siz(pos_len); int len_T = mp2[T%siz(pos_len)]; int pre_T = T/siz(pos_len); if(pre_S >= pre_T && pre_S <= pre_T+len_T-1) return 0; if(pre_T >= pre_S && pre_T <= pre_S+len_S-1) return 1; return 2; }