#216496. [APIO 2026] APIOBike

APIOBike is a newly launched bike-sharing service in APIO City. Several stations have been set up throughout the city, allowing users to borrow or return bikes at any station. Due to its convenience and low cost, it has quickly become the most important mode of transportation in APIO City. However, APIOBike has encountered a common problem faced by all bike-sharing services: an imbalance between borrowing and returning rates across different stations. This results in some stations having very few bikes, leaving nearby residents unable to borrow one, while other stations become overstocked with bikes that local residents do not need.

To address this issue, APIOBike plans to dispatch a rebalancing truck every night to redistribute bikes across the stations, ensuring that each station maintains an appropriate number of bikes. APIO City has a total of stations, numbered . Through observation, APIOBike has found that every evening, the number of bikes at station is always a fixed value , and no one borrows or returns bikes at night. The company aims to have exactly bikes at station every morning.

Among these stations, there are dedicated roads for the rebalancing truck. Each road connects two distinct stations, and the truck is restricted to travelling only on these roads. Every road is one unit long. This network of stations is connected, ensuring that the truck can travel between any pair of stations. Every night, APIOBike must dispatch a rebalancing truck to ensure that each station has exactly bikes. The truck may start at any station and may end its route at any station.

The truck is empty at the beginning of rebalancing. Whenever the truck is at a station, the driver may load any number of bikes from the station onto the truck, or unload any number of bikes from the truck onto the station. The truck and the stations have unlimited capacities for bikes, but the number of bikes at any location must never drop below zero. The company wants to determine the minimum possible travelling distance to complete the rebalancing and its corresponding strategy.

Implementation Details

You should implement the following procedure.

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)

• : an array of length , where is the number of bikes at station each evening.
• : an array of length , where is the target number of bikes at station each morning.
• : arrays of length representing the road network. For each , the -th road connects station and station .
• This procedure is called at most times for each test case.

The procedure should return a pair of arrays of equal length , representing a rebalancing strategy:

• : the sequence of station indices visited in chronological order.
• : the net bike delivery at each visited station. For each :
  • If , the driver unloads bikes at station from the truck, increasing the bike count of the station by .
  • If , the driver loads bikes from station onto the truck, decreasing the bike count of the station by .

A valid rebalancing strategy with travelling distance must satisfy the following conditions:

• For each , .
• For each , stations and are directly connected by a road.
• For each , .
• For each station and each step , let be sum of over all steps such that and .
  • The number of bikes at station never drops below zero: .
  • After the strategy concludes, each station must contain exactly bikes:

The first line of the input should contain a single integer , the number of scenarios. A description of scenarios should follow, each in the format specified below.

Input format:

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]

Output format:

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

样例输入 1

样例输出 1

Example

Example 1

Consider the following call:

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

:::align{center} :::

There are stations in APIO City. Initially, the stations have bikes, and the goal is to have bikes at every station.

Suppose the rebalancing truck starts at station 2, and follows these steps:

• At station 2, load 2 bikes onto the truck. Station 2 now has 3 bikes, and the truck has 2 bikes.
• Move to station 1 and load 1 bike onto the truck. Station 1 now has 0 bikes, and the truck has 3 bikes.
• Move to station 3, and unload 3 bikes. Station 3 now has 3 bikes, and the truck has 0 bikes.

The total moving distance is 2. The corresponding return arrays for this strategy are and . It can be proven that this strategy achieves the minimum distance. Thus, the procedure should return ([2, 1, 3], [-2, -1, 3]).

Example 2

Consider the following call:

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

:::align{center} :::

There are stations in APIO City. Initially, the stations have bikes, and the goal is to have bikes at every station.

Suppose the rebalancing truck starts at station 0, and follows these steps:

• At station 0, load 1 bike.
• Move to station 2 and load 1 bike.
• Move to station 1 and unload 2 bikes.
• Move to station 2.
• Move to station 4 and load 2 bikes.
• Move to station 2 and unload 1 bike.
• Move to station 3 and unload 1 bike.

The total moving distance is 6. The corresponding return arrays for this strategy are and . It can be proven that this strategy achieves the minimum distance. Thus, the procedure should return ([0, 2, 1, 2, 4, 2, 3], [-1, -1, 2, 0, -2, 1, 1]).

Other valid strategies with distance 6, such as and , are also considered correct. Returning arrays with length but not a valid strategy, such as , will receive of the score.

Example 3

Consider the following call:

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

:::align{center} :::

An optimal solution is and . The procedure should return ([2, 1, 0, 1, 2, 3], [-1, 1, -1, 1, -1, 1]). Other valid strategies, such as and , are also considered correct.

This example satisfies the constraints of subtasks 2 and 3.

Constraints

• The sum of over all calls to find_rebalancing_strategy does not exceed in each test case.
• and for each such that .
• for each such that .
• It is possible to travel between any pair of stations.
• .
• There exists at least one such that and .

Subtasks and Scoring

Here, is the number of calls to find_rebalancing_strategy, and is the sum of all over all calls to find_rebalancing_strategy.

Property P: For each , and . For each , .

If the return arrays and have length exactly , where is the minimum possible travelling distance, but is not a valid strategy, you will receive of the score.