#include "bike.h"
#include <bits/stdc++.h>
using namespace std;
std::pair<std::vector<int>, std::vector<long long>>
find_rebalancing_strategy(int N, std::vector<int> A, std::vector<int> B,
std::vector<int> U, std::vector<int> V) {
vector<vector<int>> g(N);
for (int i = 0; i < N - 1; i++) {
int u = U[i], v = V[i];
g[u].push_back(v);
g[v].push_back(u);
}
vector<bool> done(N, false);
int st = -1, ed = -1, cost = -1;
int remain_vertex = N;
int rt = -1;
for (int i = 0; i < N; i++) {
if (A[i] != B[i]) {
rt = i;
break;
}
}
if (rt == -1) return {{}, {}};
vector<long long> subtree(N, 0);
auto dfs1 = [&](auto self, int now, int p) -> pair<pair<int, int>, pair<int, int>> {
pair<int, int> max_up(0, now);
pair<int, int> max_down(0, now);
subtree[now] = A[now] - B[now];
bool bad = false;
for (int i : g[now]) {
if (i == p) continue;
auto [up, down] = self(self, i, now);
int tmp = up.first + max_down.first;
if (tmp > cost) cost = tmp, st = up.second, ed = max_down.second;
tmp = down.first + max_up.first;
if (tmp > cost) cost = tmp, st = max_up.second, ed = down.second;
max_up = max(max_up, up);
max_down = max(max_down, down);
subtree[now] += subtree[i];
bad = bad || !done[i];
}
if (!bad && A[now] == B[now]) {
done[now] = true;
remain_vertex--;
max_up = {-1, now};
max_down = {-1, now};
} else {
if (subtree[now] >= 0) max_up.first++;
else max_up.first--;
if (subtree[now] <= 0) max_down.first++;
else max_down.first--;
}
return {max_up, max_down};
};
dfs1(dfs1, rt, rt);
vector<long long> subtree_diff(N, 0);
vector<int> path;
auto dfs_path = [&](auto self, int now, int p) -> bool {
subtree_diff[now] = A[now] - B[now];
bool ok = (now == ed);
for (int i : g[now]) {
if (i == p) continue;
ok = self(self, i, now) || ok;
subtree_diff[now] += subtree_diff[i];
}
if (ok) path.push_back(now);
return ok;
};
dfs_path(dfs_path, st, st);
reverse(path.begin(), path.end());
vector<int> path_index(N, -1);
for (int i = 0; i < (int)path.size(); i++) {
path_index[path[i]] = i;
}
vector<int> X;
vector<long long> Y;
auto walk = [&](int v, long long amount) {
if (X.empty() || X.back() != v) {
X.push_back(v);
Y.push_back(0);
}
Y.back() += amount;
A[v] += amount;
};
for (int i = 0; i < N; i++) {
int ptr = 0;
for (int j = 0; j < (int)g[i].size(); j++) {
if (subtree_diff[g[i][j]] > 0) {
swap(g[i][ptr++], g[i][j]);
}
}
}
auto dfs2 = [&](auto self, int now, int p) -> void {
walk(now, -A[now]);
for (int i : g[now]) {
if (i == p || done[i]) continue;
self(self, i, now);
X.push_back(now);
Y.push_back(0);
}
walk(now, B[now]);
};
for (int i = 0; i < (int)path.size(); i++) {
vector<int> todo;
while (i + 1 < (int)path.size() && subtree_diff[path[i + 1]] > 0) {
int cur = path[i];
walk(cur, -A[cur]);
todo.push_back(cur);
i++;
}
todo.push_back(path[i]);
for (int j = (int)todo.size() - 1; j >= 0; j--) {
int now = todo[j];
walk(now, -A[now]);
for (int v : g[now]) {
if (path_index[v] == -1 && !done[v]) {
dfs2(dfs2, v, now);
}
walk(now, 0);
}
}
for (int now : todo) {
walk(now, B[now]);
}
}
return {X, Y};
}
