P16452 [APIO 2026] APIOBike（暂无数据）

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]$ 辆自行车。货车可以从任意站点出发，并可以在任意站点结束行程。 再平衡开始前，货车是空的。当货车位于某个站点时，司机可以将任意数量的自行车从该站点装上车，也可以将任意数量的自行车从货车上卸到该站点。货车和站点的容量均无限制，但任何地点的自行车数量不得降至零以下。公司希望求出完成再平衡所需的**最小可能行驶距离**以及对应的策略。 ### 实现细节 你需要实现以下函数。 ```cpp std::pair find_rebalancing_strategy(int N, std::vector A, std::vector B, std::vector U, std::vector 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$ 的总和。 | **子任务** | **分值** | **附加约束** | |:-:|:-:|:-:| | $1$ | $4$ | 站点和道路满足性质 P（见下）。恰好存在一个 $i$（$0 \le i < N$）满足 $A[i] > 0$。 | | $2$ | $11$ | $T \le 10$。$N \le 7$。站点和道路满足性质 P。 | | $3$ | $16$ | 站点和道路满足性质 P。 | | $4$ | $9$ | 恰好存在一个 $i$（$0 \le i < N$）满足 $A[i] > 0$。 | | $5$ | $24$ | $\sum N \le 500$。 | | $6$ | $15$ | $\sum N \le 5000$。 | | $7$ | $21$ | 无额外约束。 | 性质 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 完成