背景

在洛谷评测本题，无需使用头文件 bike.h。

题目描述

APIOBike 是 APIO 市新推出的共享单车服务。市内已设立了若干个站点，用户可以在任意站点借车或还车。凭借其便利性与低成本，APIOBike 迅速成为 APIO 市最重要的交通方式。然而，APIOBike 遇到了所有共享单车服务都面临的共同问题：不同站点的借车率与还车率不平衡。这导致某些站点的自行车非常少，附近居民无车可借；而另一些站点自行车堆积过多，当地居民却用不上。

为解决这个问题，APIOBike 计划每晚派出一辆再平衡货车，在各站点间重新调配自行车，使每个站点都保有适当数量的自行车。APIO 市共有 $N$ 个站点，编号为 $0, 1, \dots, N - 1$。通过观察，APIOBike 发现每晚站点 $i$ 的自行车数总是一个固定值 $A[i]$，且夜间无人借车或还车。公司希望每天早上站点 $i$ 的自行车数恰好为 $B[i]$。

在这 $N$ 个站点之间，有 $N - 1$ 条专供再平衡货车行驶的道路。每条道路连接两个不同的站点，且货车只允许在这些道路上行驶。每条道路的长度均为 $1$ 单位。这个站点网络是连通的，保证货车可以在任意两站点间移动。每晚，APIOBike 必须派出一辆再平衡货车，以确保每个站点 $i$ 都恰好拥有 $B[i]$ 辆自行车。货车可以从任意站点出发，并可以在任意站点结束行程。

再平衡开始前，货车是空的。当货车位于某个站点时，司机可以将任意数量的自行车从该站点装上车，也可以将任意数量的自行车从货车上卸到该站点。货车和站点的容量均无限制，但任何地点的自行车数量不得降至零以下。公司希望求出完成再平衡所需的最小可能行驶距离以及对应的策略。

实现细节

你需要实现以下函数。

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)

• $A$：长度为 $N$ 的数组，其中 $A[i]$ 是每晚站点 $i$ 的自行车数量。
• $B$：长度为 $N$ 的数组，其中 $B[i]$ 是每天早上站点 $i$ 的目标自行车数量。
• $U, V$：长度均为 $N - 1$ 的数组，表示道路网络。对于每个 $0 \le i < N - 1$，第 $i$ 条道路连接站点 $U[i]$ 与站点 $V[i]$。
• 对于每个测试用例，该函数最多被调用 $150\,000$ 次。

该函数应返回一对长度相等的数组 $(X, Y)$，长度均为 $k + 1$，表示一个再平衡策略：

• $X$：按时间顺序依次访问的站点编号序列。
• $Y$：在每个被访问站点的净自行车交付量。对于每个 $0 \le j \le k$：
  • 若 $Y[j] \ge 0$，司机在站点 $X[j]$ 将 $Y[j]$ 辆自行车从货车卸下，使该站点的自行车数增加 $Y[j]$。
  • 若 $Y[j] < 0$，司机从站点 $X[j]$ 将 $-Y[j]$ 辆自行车装上货车，使该站点的自行车数减少 $-Y[j]$。

一个行驶距离为 $k$ 的有效再平衡策略 $(X, Y)$ 必须满足以下条件：

• 对于每个 $0 \le j \le k$，$0 \le X[j] < N$。
• 对于每个 $0 \le j < k$，站点 $X[j]$ 与 $X[j + 1]$ 由一条道路直接相连。
• 对于每个 $0 \le j \le k$，$\sum_{t=0}^{j} Y[t] \le 0$。
• 对于每个站点 $0 \le i < N$ 以及每个步骤 $0 \le j \le k$，令 $S_{i,j}$ 为所有满足 $0 \le t \le j$ 且 $X[t] = i$ 的步骤 $t$ 对应的 $Y[t]$ 之和。
  • 站点 $i$ 的自行车数量从未降至零以下：$A[i] + S_{i,j} \ge 0$。
  • 策略执行完毕后，每个站点 $i$ 必须恰好拥有 $B[i]$ 辆自行车：$A[i] + S_{i,k} = B[i]$。

输入格式

第一行应包含一个整数 $T$，表示场景的数量。接下来是对 $T$ 个场景的描述，每个场景的格式如下所示。

输入格式：

N
A[0] A[1] ... A[N-1]
B[0] B[1] ... B[N-1]
U[0] V[0]
U[1] V[1]
...
U[N-2] V[N-2]

输出格式

输出格式：

k
X[0] X[1] ... X[k]
Y[0] Y[1] ... Y[k]

提示

样例

样例 1

考虑以下调用：

find_rebalancing_strategy(4,
                          [10, 1, 5, 0],
                          [10, 0, 3, 3],
                          [0, 1, 1],
                          [1, 2, 3])

:::align{center} :::

APIO 市有 $N = 4$ 个站点。初始时，各站点分别有 $A = [10, 1, 5, 0]$ 辆自行车，目标是使每个站点的自行车数变为 $B = [10, 0, 3, 3]$。

假设再平衡货车从站点 2 出发，并按以下步骤操作：

• 在站点 2，装 2 辆自行车上车。站点 2 还剩 3 辆，货车有 2 辆。
• 移动到站点 1，装 1 辆自行车上车。站点 1 还剩 0 辆，货车有 3 辆。
• 移动到站点 3，卸下 3 辆自行车。站点 3 现有 3 辆，货车有 0 辆。

总行驶距离为 2。该策略对应的返回数组为 $X = [2, 1, 3]$ 和 $Y = [-2, -1, 3]$。可以证明该策略达到了最小距离。因此，函数应返回 ([2, 1, 3], [-2, -1, 3])。

样例 2

考虑以下调用：

find_rebalancing_strategy(5,
                          [3, 0, 1, 2, 2],
                          [2, 2, 1, 3, 0],
                          [2, 2, 2, 2],
                          [0, 4, 3, 1])

:::align{center} :::

APIO 市有 $N = 5$ 个站点。初始时，各站点分别有 $A = [3, 0, 1, 2, 2]$ 辆自行车，目标是使每个站点的自行车数变为 $B = [2, 2, 1, 3, 0]$。

假设再平衡货车从站点 0 出发，并按以下步骤操作：

• 在站点 0，装 1 辆车。
• 移动到站点 2，装 1 辆车。
• 移动到站点 1，卸 2 辆车。
• 移动到站点 2。
• 移动到站点 4，装 2 辆车。
• 移动到站点 2，卸 1 辆车。
• 移动到站点 3，卸 1 辆车。

总行驶距离为 6。该策略对应的返回数组为 $X = [0, 2, 1, 2, 4, 2, 3]$ 和 $Y = [-1, -1, 2, 0, -2, 1, 1]$。可以证明该策略达到了最小距离。因此，函数应返回 ([0, 2, 1, 2, 4, 2, 3], [-1, -1, 2, 0, -2, 1, 1])。

其他距离为 6 的有效策略，例如 $X = [0, 2, 3, 2, 4, 2, 1]$ 和 $Y = [-1, 0, 1, 0, -2, 0, 2]$，同样被视为正确。若返回的数组 $X, Y$ 长度恰好为 $7 = 6 + 1$ 但不是有效策略（例如 $X = Y = [0, 0, 0, 0, 0, 0, 0]$），将获得 $50\%$ 的分数。

样例 3

考虑以下调用：

find_rebalancing_strategy(4,
                          [3, 0, 5, 0],
                          [2, 2, 3, 1],
                          [0, 1, 2],
                          [1, 2, 3])

:::align{center} :::

一个最优解为 $X = [2, 1, 0, 1, 2, 3]$ 和 $Y = [-1, 1, -1, 1, -1, 1]$。函数应返回 ([2, 1, 0, 1, 2, 3], [-1, 1, -1, 1, -1, 1])。其他有效策略，如 $X = [2, 1, 0, 1, 2, 3]$ 和 $Y = [-2, 2, -1, 0, 0, 1]$，同样被视为正确。

此样例满足子任务 2 和子任务 3 的约束条件。

数据范围

• $2 \le N \le 300\,000$
• 在每个测试用例中，所有 find_rebalancing_strategy 调用的 $N$ 之和不超过 $300\,000$。
• 对于每个满足 $0 \le i < N$ 的 $i$，有 $0 \le U[i], V[i] < N$ 且 $U[i] \neq V[i]$。
• 对于每个满足 $0 \le i < N$ 的 $i$，有 $0 \le A[i], B[i] \le 10^9$。
• 任意两个站点之间均可通行。
• $\sum_{i=0}^{N-1} A[i] = \sum_{i=0}^{N-1} B[i]$。
• 至少存在一个 $i$（$0 \le i < N$）满足 $A[i] \neq B[i]$。

子任务与评分

这里，$T$ 表示 find_rebalancing_strategy 的调用次数，$\sum N$ 表示所有调用中 $N$ 的总和。

性质 P：对于每个 $0 \le i < N - 1$，有 $U[i] = i$ 且 $V[i] = i + 1$。对于每个 $0 \le i < N$，有 $A[i] \neq B[i]$。

如果返回的数组 $X$ 和 $Y$ 的长度恰好为 $k^* + 1$（其中 $k^*$ 是最小可能行驶距离），但 $(X, Y)$ 不是有效策略，你将获得该测试点 $50\%$ 的分数。

翻译由 DeepSeek V4 Pro 完成