#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef unsigned long long ll;
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define pi pair<ll, ll>
#define pll pair<long long, long long>
#define vi vector<ll>
#define vll vector<long long>
#define vpi vector<pair<ll,ll>>
#define vpll vector<pair<long long, long long>>
#define pb push_back
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)(x).size()
#define forall(it,x) for(auto& it:(x))
#define mp make_pair
pi operator+(pi a, pi b) { return mp(a.ff+b.ff, a.ss+b.ss); }
pi operator-(pi a, pi b) { return mp(a.ff-b.ff, a.ss-b.ss); }
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "multi.h"
vector<ll> rep;
ll Find(ll v) {
return rep[v]==v ? v : rep[v] = Find(rep[v]);
}
bool Union(ll a, ll b) {
a=Find(a);
b=Find(b);
if(a==b) return 0;
if(a < b) swap(a,b);
rep[a] = b;
return 1;
}
ll inf = 1ULL<<60;
ll end_of_boruvka = 3;
std::vector<unsigned long long> strategy(int32_t N, int32_t r, int32_t my,
std::vector<unsigned long long> A, std::vector<unsigned long long> B) {
rep.assign(N, 0);
for(ll i=0; i<N; ++i) rep[i] = i;
ll X = B[0];
if(r==0) {
for(ll i=0; i<N; ++i) rep[i] = i;
} else if(r<=end_of_boruvka) {
if(r > 1) {
for(ll i=1; i<N; ++i) {
rep[i] = B[i]%(1ULL<<8);
B[i] /= (1ULL<<8);
}
vector<pi> best(N, {inf,0});
for(ll i=1; i<N; ++i) {
ll nei = B[i]%(1ULL<<8);
B[i] /= (1ULL<<8);
best[Find(i)] = min(best[Find(i)], {B[i], nei});
}
for(ll i=1; i<N; ++i) {
if(best[i].first < inf && Union(i, best[i].second)) {
X+=best[i].first;
}
}
} else {
vector<pi> best(N, {inf,0});
for(ll i=1; i<N; ++i) {
ll nei = B[i]%(1ULL<<8);
B[i] /= (1ULL<<8);
best[Find(i)] = min(best[Find(i)], {B[i], nei});
}
for(ll i=1; i<N; ++i) {
if(best[i].first < inf) Union(i, best[i].second);
}
best.assign(N, {inf, 0});
for(ll i=1; i<N; ++i) {
ll nei = B[i]%(1ULL<<8);
B[i] /= (1ULL<<8);
best[Find(i)] = min(best[Find(i)], {B[i], nei});
}
for(ll i=1; i<N; ++i) {
if(best[i].first < inf && Union(i, best[i].second)) {
X+=best[i].first;
}
}
}
}
if(r==0) {
pi best = {inf,0};
for(ll i=0; i<N; ++i) if(i!=my) best = min(best, {A[i], i});
ll value = best.second;
pi best2 = {inf, 0};
for(ll i=0; i<N; ++i) if(i!=my && i!=best.second) best2 = min(best2, {A[i], i});
if(best2.first == inf) best2 = best;
value += (best2.second << 8) + (best2.first << 16);
if(my==0) value = X;
vector<ll> C(N, value);
return C;
} else if(r < end_of_boruvka) {
pi best = {inf,0};
for(ll i=0; i<N; ++i) if(Find(i)!=Find(my)) best = min(best, {A[i], i});
ll value = (best.first<<16) + (best.second<<8) + Find(my);
if(my==0) value = X;
vector<ll> C(N, value);
return C;
} else if(r==end_of_boruvka) {
set<ll> V;
for(ll i=0; i<N; ++i) V.insert(Find(i));
vector<ll> S;
for(auto x : V) S.pb(x);
map<ll, ll> mapa;
for(ll i=0; i<S.size(); ++i) mapa[S[i]] = i;
vector<vector<ll>> F(N+1, vector<ll>(N+1));
ll idx = 1;
for(ll i=0; i<S.size(); ++i) {
for(ll j=i+1; j<S.size(); ++j) {
F[i][j] = idx++;
}
}
vector<ll> send(N, Find(my));
vector<ll> best(N, inf);
for(ll j=0; j<N; ++j) {
best[Find(j)] = min(best[Find(j)], A[j]);
}
for(ll j=0; j<N; ++j) {
if(best[j]==inf || Find(my)==j) continue;
ll X = min(Find(my), j);
ll Y = max(Find(my), j);
X = mapa[X];
Y = mapa[Y];
send[F[X][Y]] += (best[j] << 8);
}
if(my==0) {
vector<ll> ssss(N, X);
return ssss;
}
pi my_best = {inf,0};
for(ll i=0; i<N; ++i) if(i!=my) my_best = min(my_best, {A[i], i});
send[0] = (my_best.first << 8) + my_best.second;
return send;
} else if(r==end_of_boruvka+1) {
if(my) {
for(ll i=1; i<N; ++i) {
rep[i] = B[i]%(1ULL << 8);
B[i] /= (1ULL << 8);
}
set<ll> V;
for(ll i=0; i<N; ++i) V.insert(rep[i]);
vector<ll> S;
for(auto x : V) S.pb(x);
vector<vector<ll>> F(N+1, vector<ll>(N+1));
ll idx = 1;
ll ff_sender=-1, ss_sender=-1;
for(ll i=0; i<S.size(); ++i) {
for(ll j=i+1; j<S.size(); ++j) {
if(idx==my) {
ff_sender = S[i];
ss_sender = S[j];
}
F[i][j] = idx++;
}
}
ll best = inf;
for(ll i=1; i<N; ++i) {
if(rep[i] != ff_sender && rep[i] != ss_sender) continue;
best = min(best, B[i]);
}
if(best == inf) best = 0;
vector<ll> C(N, rep[my] + (best << 8));
return C;
} else {
rep.assign(N,0);
for(ll i=0; i<N; ++i) rep[i] = i;
for(ll i=1; i<N; ++i) {
ll nei = B[i] % (1ULL << 8);
B[i] /= (1ULL << 8);
if(Union(i, nei)) {
X += B[i];
}
}
vector<ll> C(N, X);
return C;
}
} else if(r==end_of_boruvka+2) {
if(my) {
vector<ll> C(N,0);
return C;
}
for(ll i=1; i<N; ++i) {
rep[i] = B[i]%(1ULL << 8);
B[i] /= (1ULL << 8);
}
set<ll> V;
for(ll i=0; i<N; ++i) V.insert(rep[i]);
vector<ll> S;
for(auto x : V) S.pb(x);
vector<vector<ll>> F(N+1, vector<ll>(N+1));
ll idx = 1;
vector<pair<ll, pi>> e;
for(ll i=0; i<S.size(); ++i) {
for(ll j=i+1; j<S.size(); ++j) {
e.pb({B[idx], {S[i], S[j]}});
idx++;
}
}
sort(all(e));
for(auto[w, stat] : e) {
auto[a,b] = stat;
if(Union(a,b)) {
X += w;
}
}
// cout << X << "\n";
return {X};
}
return {X};
}
