作者： chenchen

**Note: The time limit for this problem is 4s, twice the default.**

Farmer John has a binary tree with N nodes where the nodes are numbered from 1 to N (1≤N<2⋅10⁵ and N is odd). For i>1, the parent of node i is ⌊i/2⌋. Each node has an initial integer value a_i, and a cost c_i to change the initial value to any other integer value (0≤a_i,c_i ≤10⁹).

He has been tasked by the Federal Bovine Intermediary (FBI) with finding an approximate median value within this tree, and has devised a clever algorithm to do so.

He starts at the last node N and works his way backward. At every step of the algorithm, if a node would not be the median of it and its two children, he swaps the values of the current node and the child value that would be the median. At the end of this algorithm, the value at node 1 (the root) is the median approximation.

The FBI has also given Farmer John a list of Q (1≤Q≤2⋅10⁵) independent queries each specified by a target value m (0≤m≤10⁹). For each query, FJ will first change some of the node's initial values, and then execute the median approximation algorithm. For each query, determine the minimum possible total cost for FJ to make the output of the algorithm equal to m.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains N.

The next N lines each contain two integers a_i and c_i.

The next line contains Q.

The next Q lines each contain a target value m.

OUTPUT FORMAT (print output to the terminal / stdout):

Output Q lines, the minimum possible total cost for each target value m.

SAMPLE INPUT:

5
10 10000
30 1000
20 100
50 10
40 1
11
55
50
45
40
35
30
25
20
15
10
5

SAMPLE OUTPUT:

111
101
101
100
100
100
100
0
11
11
111

To make the median approximation equal 40, FJ can change the value at node 3 to 60. This costs c₃=100.

To make the median approximation equal 45, FJ can change the value at node 3 to 60 and the value at node 5 to 45. This costs c₃+c₅=100+1=101.

SCORING:

Inputs 2-4: N,Q≤50
Inputs 5-7: N,Q≤1000
Inputs 8-16: No additional constraints

Problem credits: Suhas Nagar and Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie's garden has N plants labeled 1 through N(2≤N≤5⋅10⁵) from left to right. Bessie knows that plant i requires at least wi (0≤w_i≤10⁶) units of water.

Bessie has a very peculiar irrigation system with N−1 canals, numbered 1 through N−1. Each canal i has an associated unit cost c_i (1≤c_i≤10⁶), such that Bessie can pay cik to provide plants i and i+1 each with k units of water, where k is a non-negative integer.

Bessie is busy and may not have time to use all the canals. For each 2≤i≤N compute the minimum cost required to water plants 1 through i using only the first i−1 canals.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains a single positive integer N.

The second line contains N space-separated integers w₁,…,w_N.

The third line contains N−1 space-separated integers c₁,…,c_N−1.

OUTPUT FORMAT (print output to the terminal / stdout):

Output N−1 newline-separated integers. The (i−1)th integer should contain the minimum cost to water the first i plants using the first i−1 canals.

SAMPLE INPUT:

3
39 69 33
30 29

SAMPLE OUTPUT:

2070
2127

The minimum cost to water the first 2 plants using the first canal is to pay 30⋅69=2070 by using the first canal 69 times.

The minimum cost to water the first 3 plants is to use the first canal 39 times and the second canal 33 times, paying 39⋅30+29⋅33=2127.

SAMPLE INPUT:

3
33 82 36
19 1

SAMPLE OUTPUT:

1558
676

SAMPLE INPUT:

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

SAMPLE OUTPUT:

623
4099
4114
6269
6272
6827
8827

SCORING:

Input 4: N≤200, and all w_i ≤200.
Inputs 5-6: All w_i ≤200.
Inputs 7-10: N≤5000.
Inputs 11-14: All w_i and c_i are generated independently and uniformly at random.
Inputs 15-19: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie is experimenting with a powerful hoof implant that has the ability to create massive shock waves. She has N (2≤N≤10⁵) tiles lined up in front of her, which require powers of at least p₀,p₁,…,p_N−1 to break, respectively (0≤p_i≤10¹⁸).

Bessie can apply power by punching a specific tile but due to the strange nature of her implant, it will not apply any power to the tile she punches. Instead, if she chooses to punch tile x once, where x is an integer in [0,N−1], it applies |i−x| power to tile i for all integers i in the range [0,N−1]. This power is also cumulative, so applying 2 power twice to a tile will apply a total of 4 power to the tile.

Please determine the fewest number of punches required to break all the tiles.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T(1≤T≤100) representing the number of test cases.

Line 2t contains a single integer N, the number of tiles in test case t.

Line 2t+1 contains N space separated numbers p₀,p₁,…,p_N−1 representing that tile i takes p_i  power to be broken.

It is guaranteed that the sum of all N in a single input does not exceed 5⋅10⁵.

OUTPUT FORMAT (print output to the terminal / stdout):

T lines, the ith line representing the answer to the ith test case.

SAMPLE INPUT:

6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000

SAMPLE OUTPUT:

2
3
2
4
4
2000000000000000000

For the first test, the only way for Bessie to break all the tiles with two punches is to punch 0 twice, applying total powers of [0,2,4,6,8] respectively.

For the second test, one way for Bessie to break all the tiles with three punches is to punch 0, 2, and 4 one time each, applying total powers of [6,5,4,5,6] respectively.

For the third test, one way for Bessie to break all the tiles with two punches is to punch 0 and 1 one time each, applying total powers of [1,1,3,5,7] respectively.

SCORING:

Input 2: All p_i are equal.
Inputs 3-6: N≤100
Inputs 7-14: No additional constraints.

Problem credits: Suhas Nagar

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划

Bessie has a simple undirected graph with vertices labeled 1…N(2≤N≤750). She generates a depth-first search (DFS) order of the graph by calling the function dfs(1), defined by the following C++ code. Each adjacency list (adj[i] for all 1≤i≤N) may be permuted arbitrarily before starting the depth first search, so a graph can have multiple possible DFS orders.

vector<bool> vis(N + 1);
vector<vector<int>> adj(N + 1); // adjacency list
vector<int> dfs_order;

void dfs(int x) {
if (vis[x]) return;
vis[x] = true;
dfs_order.push_back(x);
for (int y : adj[x]) dfs(y);
}

You are given the initial state of the graph as well as the cost to change the state of each edge. Specifically, for every pair of vertices (i,j) satisfying 1≤i<j≤N, you are given an integer a_i,j(0<|a_i,j|≤1000) such that

If a_i,j >0, edge (i,j) is not currently in the graph, and can be added for cost a_i,j.
If a_i,j<0, edge (i,j)is currently in the graph, and can be removed for cost −a_i,j.

Determine the minimum total cost to change the graph so that [1,2…,N]
is a possible DFS ordering.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

Then N−1 lines follow. The j−1
th line contains a_1,j ,   a_2,j,…,a_j−1,_j separated by spaces.

OUTPUT FORMAT (print output to the terminal / stdout):

The minimum cost to change the graph so that [1,2,…,N]
is a possible DFS ordering.

SAMPLE INPUT:

4
1
2 3
40 6 11

SAMPLE OUTPUT:

10

Initially, the graph contains no edges. (1,2),(2,3),(2,4)
can be added for a total cost of 1+3+6. The graph now has two possible DFS orderings: [1,2,3,4],[1,2,4,3].

SAMPLE INPUT:

5
-1
10 -2
10 -7 10
-6 -4 -5 10

SAMPLE OUTPUT:

5

Initially, the graph contains edges (1,2),(2,3),(2,4),(1,5),(2,5),(3,5). Edge (3,5) can be removed for a cost of 5.

SAMPLE INPUT:

4
-1
-2 300
4 -5 6

SAMPLE OUTPUT:

9

Initially, the graph contains edges (1,2),(1,3),(2,4). Edge (2,4)
can be removed and edge (1,4) can be added for a total cost of 5+4=9.

SCORING:

Inputs 4-9: All a_i,j >0
Inputs 10-16: N≤50
Inputs 17-23: No additional constraints.

Problem credits: Benjamin Qi

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划