#include "souvenirs.h"
// #include "debug.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
void buy_souvenirs(int N, long long P0) {
vector<ll> sum(N);
vector<int> cnt(N);
int left = N - 1;
vector<vector<int>> dep(N);
dep[0].push_back(0);
sum[0] = P0;
auto relax = [&](ll y) -> void {
auto now = transaction(y);
int x = now.first[0];
vector<int> add;
ll cost = y - now.second;
for (int i : now.first) {
cnt[i] += 1;
if (sz(dep[i]) == 1) {
cost -= sum[i];
} else {
add.push_back(i);
}
}
sum[x] = cost;
dep[x] = add;
};
auto update = [&]() -> void {
for (int i = N - 1; i >= 0; --i) {
vector<int> add;
ll cost = sum[i];
for (int j : dep[i]) {
if (j == i) {
add.push_back(j);
continue;
}
if (sz(dep[j]) == 1) cost -= sum[j];
else add.push_back(j);
}
left -= sz(dep[i]) == 1;
dep[i] = add;
sum[i] = cost;
}
};
while (left > 0) {
for (int i = N - 1; i >= 0; --i) {
if (sz(dep[i]) == 0) {
while (sz(dep[i]) == 0) i -= 1;
relax(sum[i] / sz(dep[i]) - (sz(dep[i]) == 1));
break;
}
}
left = N;
update();
}
for (int i = 0; i < N; ++i) {
while (cnt[i] < i) {
cnt[i] += 1;
transaction(sum[i]);
}
}
}
