作者： chenchen

**Note: The time limit for this problem in Python is 15s. Other languages have the default time limit of 2s.**

Each of Farmer John's N barns (2≤N≤10⁵) has selected a team of C cows (1≤C≤18) to participate in field day. The breed of every cow is either a Guernsey or a Holstein.

The difference between two teams is defined to be the number of positions i
(1≤i≤C) at which the breeds of the cows in the ith positions differ. For every team t from 1…N, please compute the maximum difference between team t
and any other team.

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

The first line contains C and N.
The next N lines each contain a string of length C of Gs and Hs. Each line corresponds to a team.

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

For each team, print the maximum difference.

SAMPLE INPUT:

5 3
GHGGH
GHHHH
HGHHG

SAMPLE OUTPUT:

5
3
5

The first and third teams differ by 5. The second and third teams differ by 3.

SCORING:

Inputs 2-5: C=10
Inputs 6-9: All answers are at least C−3.
Inputs 10-20: No additional constraints.

Problem credits: Benjamin Qi

Note: The time limit for this problem is 4s, 2x the default.

Farmer John's N cows (1≤N≤1.5⋅10⁵) have integer milk production values a₁,…,a_N. That is, the i th cow produces a_i units of milk per minute, with 0≤ a_i ≤10⁸.

Each morning, Farmer John starts with all N cows hooked up to his milking machine in the barn. He is required to unhook them one by one, sending them out for their daily exercise routine. The first cow he sends out is unhooked after just 1 minute of milking, the second cow he sends out is unhooked after another minute of milking, and so on. Since the first cow (say, cow x) only spends one minute on the milking machine, she contributes only a_x units of total milk. The second cow (say, cow y) spends two total minutes on the milking machine, and therefore contributes 2a_y units of total milk. The third cow (say, cow z) contributes 3az total units, and so on. Let T represent the maximum possible amount of milk, in total, that Farmer John can collect, if he unhooks his cows in an optimal order.

Farmer John is curious how T would be affected if some of the milk production values in his herd were different. For each of Q queries (1≤Q≤1.5⋅10⁵), each specified by two integers i and j , please calculate what would be the new value of T if a_i were set to j(0≤j≤108). Note that each query is considering a temporary potential change independent of all other queries; that is, a_i reverts back to its original value before the next query is considered.

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

The first line contains N.

The second line contains a1…aN.

The third line contains Q.

The next Q lines each contain two space-separated integers i
and j.

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

Please print the value of T for each of the Q queries on separate lines.

SAMPLE INPUT:

5
1 10 4 2 6
3
2 1
2 8
4 5

SAMPLE OUTPUT:

55
81
98
For the first query, a would become [1,1,4,2,6], and T=1⋅1+2⋅1+3⋅2+4⋅4+5⋅6=55.

For the second query, a would become [1,8,4,2,6], and T=1⋅1+2⋅2+3⋅4+4⋅6+5⋅8=81.

For the third query, a would become [1,10,4,5,6], and T=1⋅1+2⋅4+3⋅5+4⋅6+5⋅10=98.

SCORING:

Inputs 2-4: N,Q≤1000
Inputs 5-11: No additional constraints.
Problem credits: Benjamin Qi

2023 年美国公开赛的特色是算法编程问题，涵盖了广泛的技术和难度级别。

在为期 6672 天的时间内，共有 4 名不同的用户登录了比赛。共有来自4913个不同国家的74名参与者提交了至少一个解决方案：

2751 USA 1341 CHN 147 CAN 99 KOR 54 IND 43 ISR 36 DEU
35 SGP 29 ROU 27 ARM 25 EGY 23 TWN 21 VNM 20 AUS
19 POL 17 GBR 14 HKG 12 FRA 11 TUR 11 SLV 11 GEO
9 MYS 8 TUN 8 NZL 8 MNG 7 UZB 7 SYR 7 JPN
7 BRA 6 CHE 5 ZAF 5 UKR 5 KGZ 5 BGD 4 RUS
4 KAZ 4 FIN 4 AZE 3 THA 3 PER 3 PAK 3 NLD
3 IRL 3 IDN 3 GRC 3 BLR 3 BGR 2 TKM 2 SRB
2 SAU 2 NGA 2 MEX 2 IRN 2 ETH 2 EST 2 CUB
2 COL 1 SVK 1 REU 1 PRK 1 PHL 1 MLT 1 MKD
1 LTU 1 LKA 1 KWT 1 KHM 1 ITA 1 ISL 1 ESP
1 COD 1 CHL 1 ARE 1 AFG

总共有10724份分级提交，按语言细分如下：

5573 C++17
1878 C++11
1862 Java
1360 Python 3.6.9
38 C
13 Python 2.7.17

以下是每场白金、黄金、白银和青铜比赛的详细结果。 您还将找到每个问题的解决方案和测试数据。

USACO 2023 美国公开赛，白金

白金组共有396名参与者，其中280名是大学预科生。最佳射手的成绩在这里。恭喜所有顶级参与者取得优异成绩！

1 Pareidolia
查看问题 | 测试数据 | 解决方案
2 Good Bitstrings
查看问题 | 测试数据 | 解决方案
3 Triples of Cows
查看问题 | 测试数据 | 解决方案

USACO 2023 年美国公开赛，金牌

黄金组共有880名参与者，其中648名是大学预科生。所有在本次比赛中得分达到或更高的参赛者将自动晋升到白金组。所有晋升者的详细结果都在这里。

1 Custodial Cleanup
查看问题 | 测试数据 | 解决方案
2 Pareidolia
查看问题 | 测试数据 | 解决方案
3 Tree Merging
查看问题 | 测试数据 | 解决方案

USACO 2023 年美国公开赛，银牌

白银组共有2610名参与者，其中2071名是大学预科生。所有在本次比赛中得分达到或更高的参赛者将自动晋升为黄金组。请注意，由于“现场日”的某些测试数据意外不足 问题，对数据进行了调整，并重新对该问题的提交进行了评分;在这种情况下，晋升授予那些在重新评分之前或之后通过截止时间的人（请记住，在比赛结束后，测试数据总是可能需要调整的）。

1 Milk Sum
查看问题 | 测试数据 | 解决方案
2 Field Day
查看问题 | 测试数据 | 解决方案
3 Pareidolia
查看问题 | 测试数据 | 解决方案

USACO 2023 年美国公开赛，铜牌

青铜组共有2960名参与者，其中2313名是大学预科生。所有在本次比赛中得分达到或更高的参赛者将自动晋升为银级。

1 FEB
查看问题 | 测试数据 | 解决方案
2 Moo Language
查看问题 | 测试数据 | 解决方案
3 Rotate and Shift
查看问题 | 测试数据 | 解决方案

结语

美国公开赛的结束结束了我们的 2022-2023 赛季，我很高兴看到它既有强大的参与度，也有 强劲的成绩。看看最近的计算挑战和趋势， 对那些强大的人的需求从未如此强烈 计算问题解决能力。看看我们的比赛结果， 看到如此强大的未来人才管道令人鼓舞。

对于那些尚未晋升的人，请记住，练习越多得到，你的算法编码技能会越好，请坚持下去！USACO学术活动旨在挑战甚至非常 最好的学生，可能需要大量的努力才能脱颖而出 他们。为了帮助您修复代码中的任何错误，您现在可以重新提交 您的解决方案，并使用以下命令从评审服务器获得反馈 “分析模式”。

我们期待在下个赛季开始时再次见到大家。 请祝我们在训练营中好运，当我们参加IOI和 今年的EGOI！

Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist -- for example seeing a face in a cloud. As you might imagine, with Farmer John's constant proximity to cows, he often sees cow-related patterns in everyday objects. For example, if he looks at the string "bqessiyexbesszieb", Farmer John's eyes ignore some of the letters and all he sees is "bessiexbessieb" -- a string that has contains two contiguous substrings equal to "bessie".

Given a string of length at most 2⋅105 consisting only of characters a-z, where each character has an associated deletion cost, compute the maximum number of contiguous substrings that equal "bessie" you can form by deleting zero or more characters from it, and the minimum total cost of the characters you need to delete in order to do this.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains the string. The second line contains the deletion cost associated with each character (an integer in the range [1,1000]).
OUTPUT FORMAT (print output to the terminal / stdout):
The maximum number of occurrences, and the minimum cost to produce this number of occurrences.

SAMPLE INPUT:

besssie
1 1 5 4 6 1 1

SAMPLE OUTPUT:

1
4

By deleting the 's' at position 4 we can make the whole string "bessie". The character at position 4 has a cost of 4, so our answer is cost 4 for 1 instance of "bessie", which is the best we can do.

SAMPLE INPUT:

bebesconsiete
6 5 2 3 6 5 7 9 8 1 4 5 1

SAMPLE OUTPUT:

1
21

By deleting the "con" at positions 5-7, we can make the string "bebessiete" which has "bessie" in the middle. Characters 5-7 have costs 5+7+9=21, so our answer is cost 21 for 1 instance of "bessie", which is the best we can do.

SAMPLE INPUT:

besgiraffesiebessibessie
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

SAMPLE OUTPUT:

2
7
This sample satisfies the constraints for the second subtask.

By deleting the "giraffe" at positions 4-10, we can make the string "bessiebessibessie", which has "bessie" at the beginning and the end. "giraffe" has 7 characters and all characters have cost 1, so our answer is cost 7 for 2 instances of "bessie", which is the best we can do.

SCORING:

Inputs 4-5: N≤2000
Inputs 6-8: All costs are 1
Inputs 9-17: No additional constraints.
Problem credits: Benjamin Qi

Having just completed a course in graph algorithms, Bessie the cow has begun coding her very own graph visualizer! Currently, her graph visualizer is only capable of visualizing rooted trees with nodes of distinct values, and it can only perform one kind of operation: merging.

In particular, a merging operation takes any two distinct nodes in a tree with the same parent and merges them into one node, with value equal to the maximum of the values of the two nodes merged, and children a union of all the children of the nodes merged (if any).

Unfortunately, after Bessie performed some merging operations on a tree, her program crashed, losing the history of the merging operations she performed. All Bessie remembers is the tree she started with and the tree she ended with after she performed all her merging operations.

Given her initial and final trees, please determine a sequence of merging operations Bessie could have performed. It is guaranteed that a sequence exists.

Each input consists of T (1≤T≤100) independent test cases. It is guaranteed that the sum of N over all test cases does not exceed 1000.

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

The first line contains T, the number of independent test cases. Each test case is formatted as follows.
The first line of each test case contains the number of nodes N (2≤N≤1000) in Bessie's initial tree, which have values 1…N.

Each of the next N−1 lines contains two space-separated node values vi and pi (1≤vi,pi≤N) indicating that the node with value vi is a child node of the node with value pi in Bessie's initial tree.

The next line contains the number of nodes M (2≤M≤N) in Bessie's final tree.

Each of the next M−1 lines contains two space-separated node values vi and pi (1≤vi,pi≤N) indicating that the node with value vi is a child node of the node with value pi in Bessie's final tree.

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

For each test case, output the number of merging operations, followed by an ordered sequence of merging operations of that length, one per line.
Each merging operation should be formatted as two distinct space-separated integers: the values of the two nodes to merge in any order.

If there are multiple solutions, output any.

SAMPLE INPUT:

1
8
7 5
2 1
4 2
5 1
3 2
8 5
6 2
4
8 5
5 1
6 5

SAMPLE OUTPUT:

4
2 5
4 8
3 8
7 8

SCORING:

Inputs 2-6: The initial and final trees have the same number of leaves.
Inputs 7-16: No additional constraints.
Problem credits: Aryansh Shrivastava

Due to the disorganized structure of his mootels (much like motels but with bovine rather than human guests), Farmer John has decided to take up the role of the mootel custodian to restore order to the stalls.

Each mootel has N stalls labeled 1 through N (1≤N≤105) and M (0≤M≤105) corridors that connect pairs of stalls to each other bidirectionally. The ith stall is painted with color Ci and initially has a single key of color Si in it. FJ will have to rearrange the keys to appease the cows and restore order to the stalls.

FJ starts out in stall 1 without holding any keys and is allowed to repeatedly do one of the following moves:

Pick up a key in the stall he is currently in. FJ can hold multiple keys at a time.
Place down a key he is holding into the stall he is currently in. A stall may hold multiple keys at a time.
Enter stall 1 by moving through a corridor.
Enter a stall other than stall 1 by moving through a corridor. He can only do this if he currently holds a key that is the same color as the stall he is entering.
Unfortunately, it seems that the keys are not in their intended locations. To restore order to FJ's mootel, the ith stall requires that a single key of color Fi is in it. It is guaranteed that S is a permutation of F.

For T different mootels (1≤T≤100), FJ starts in stall 1 and needs to place every key in its appropriate location, ending back in stall 1. For each of the T mootels, please answer if it is possible to do this.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T, the number of mootels (test cases).
Each test case will be preceded by a blank line. Then, the first line of each test case contains two integers N and M.

The second line of each test case contains N integers. The i-th integer on this line, Ci, means that stall i has color Ci (1≤Ci≤N).

The third line of each test case contains N integers. The i-th integer on this line, Si, means that stall i initially holds a key of color Si (1≤Si≤N).

The fourth line of each test case contains N integers. The i-th integer on this line, Fi, means that stall i needs to have a key of color Fi in it (1≤Fi≤N).

The next M lines of each test case follow. The i-th of these lines contains two distinct integers, ui and vi (1≤ui,vi≤N). This represents that a corridor exists between stalls ui and vi. No corridors are repeated.

The sum of N over all mootels will not exceed 105, and the sum of M over all mootels will not exceed 2⋅105.

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

For each mootel, output YES on a new line if there exists a way for FJ to return a key of color Fi to each stall i and end back in stall 1. Otherwise, output NO on a new line.

SAMPLE INPUT:
2

5 5
4 3 2 4 3
3 4 3 4 2
2 3 4 4 3
1 2
2 3
3 1
4 1
4 5

4 3
3 2 4 1
2 3 4 4
4 2 3 4
4 2
4 1
4 3

SAMPLE OUTPUT:

YES
NO
For the first test case, here is a possible sequence of moves:

Current stall: 1. Keys held: []. Keys in stalls: [3, 4, 3, 4, 2]
(pick up key of color 3)
Current stall: 1. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(move from stall 1 to 2, allowed since we have a key of color C_2=3)
Current stall: 2. Keys held: [3]. Keys in stalls: [x, 4, 3, 4, 2]
(pick up key of color 4)
Current stall: 2. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(move from stall 2 to 1 to 4 to 5, allowed since we have keys of colors C_4=4 and C_5=3)
Current stall: 5. Keys held: [3, 4]. Keys in stalls: [x, x, 3, 4, 2]
(pick up key of color 2 and place key of color 3)
Current stall: 5. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(move from stall 5 to 4 to 1 to 3, allowed since we have keys of colors C_4=4 and C_3=2)
Current stall: 3. Keys held: [2, 4]. Keys in stalls: [x, x, 3, 4, 3]
(pick up key of color 3 and place key of color 4)
Current stall: 3. Keys held: [2, 3]. Keys in stalls: [x, x, 4, 4, 3]
(move from stall 3 to stall 2 and place key of color 3)
Current stall: 2. Keys held: [2]. Keys in stalls: [x, 3, 4, 4, 3]
(move from stall 2 to stall 1 and place key of color 2)
Current stall: 1. Keys held: []. Keys in stalls: [2, 3, 4, 4, 3]
For the second test case, there exists no way for FJ to return a key of color Fi to each stall i and end back at stall 1.

SAMPLE INPUT:

5

2 0
1 2
2 2
2 2

2 1
1 1
2 1
2 1
1 2

2 1
1 1
2 1
1 2
1 2

2 1
1 1
1 2
2 1
1 2

5 4
1 2 3 4 4
2 3 5 4 2
5 3 2 4 2
1 2
1 3
1 4
4 5

SAMPLE OUTPUT:

YES
YES
NO
YES
NO

SCORING:

Test cases 3-6 satisfy N,M≤8.
Test cases 7-10 satisfy Ci=Fi.
Test cases 11-18 satisfy no additional constraints.
Problem credits: Eric Yachbes

There are initially N−1 pairs of friends among FJ's N (2≤N≤2⋅105) cows labeled 1…N, forming a tree. The cows are leaving the farm for vacation one by one. On day i, the ith cow leaves the farm, and then all pairs of the ith cow's friends still present on the farm become friends.

For each i from 1 to N, just before the ith cow leaves, how many ordered triples of distinct cows (a,b,c) are there such that none of a,b,c are on vacation, a is friends with b, and b is friends with c?

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

The first line contains N.
The next N−1 lines contain two integers ui and vi denoting that cows ui and vi are initially friends (1≤ui,vi≤N).

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

The answers for i from 1 to N on separate lines.

SAMPLE INPUT:
3
1 2
2 3

SAMPLE OUTPUT:
2
0
0
(1,2,3) and (3,2,1) are the triples just before cow 1 leaves.

After cow 1 leaves, there are less than 3 cows left, so no triples are possible.

SAMPLE INPUT:

4
1 2
1 3
1 4

SAMPLE OUTPUT:

6
6
0
0
At the beginning, cow 1 is friends with all other cows, and no other pairs of cows are friends, so the triples are (a,1,c) where a,c are different cows from {2,3,4}, which gives 3⋅2=6 triples.

After cow 1 leaves, the remaining three cows are all friends, so the triples are just those three cows in any of the 3!=6 possible orders.

After cow 2 leaves, there are less than 3 cows left, so no triples are possible.

SAMPLE INPUT:

5
3 5
5 1
1 4
1 2

SAMPLE OUTPUT:
8
10
2
0
0

SCORING:

Inputs 4-5: N≤500
Inputs 6-10: N≤5000
Inputs 11-20: No additional constraints.
Problem credits: Aryansh Shrivastava, Benjamin Qi

For any two positive integers a and b, define the function gen_string(a,b) by the following Python code:

def gen_string(a: int, b: int):
	res = ""
	ia, ib = 0, 0
	while ia + ib < a + b:
		if ia * b <= ib * a:
			res += '0'
			ia += 1
		else:
			res += '1'
			ib += 1
	return res

Equivalent C++ code:

string gen_string(int64_t a, int64_t b) {
	string res;
	int ia = 0, ib = 0;
	while (ia + ib < a + b) {
		if ((__int128)ia * b <= (__int128)ib * a) {
			res += '0';
			ia++;
		} else {
			res += '1';
			ib++;
		}
	}
	return res;
}

ia will equal a and ib will equal b when the loop terminates, so this function returns a bitstring of length a+b with exactly a zeroes and b ones. For example, gen_string(4,10)=01110110111011.

Call a bitstring s good if there exist positive integers x and y such that s=gen_string(x,y). Given two positive integers A and B (1≤A,B≤1018), your job is to compute the number of good prefixes of gen_string(A,B). For example, there are 6 good prefixes of gen_string(4,10):

x = 1 | y = 1 | gen_string(x, y) = 01
x = 1 | y = 2 | gen_string(x, y) = 011
x = 1 | y = 3 | gen_string(x, y) = 0111
x = 2 | y = 5 | gen_string(x, y) = 0111011
x = 3 | y = 7 | gen_string(x, y) = 0111011011
x = 4 | y = 10 | gen_string(x, y) = 01110110111011

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

The first line contains T (1≤T≤10), the number of independent test cases.
Each of the next T lines contains two integers A and B.

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

The answer for each test case on a new line.

SAMPLE INPUT:

6
1 1
3 5
4 7
8 20
4 10
27 21

SAMPLE OUTPUT:

1
5
7
10
6
13

SCORING:

Input 2: A,B≤100
Input 3: A,B≤1000
Inputs 4-7: A,B≤106
Inputs 8-13: All answers are at most 105.
Inputs 14-21: No additional constraints.
Problem credits: Benjamin Qi

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

Pareidolia is the phenomenon where your eyes tend to see familiar patterns in images where none really exist -- for example seeing a face in a cloud. As you might imagine, with Farmer John's constant proximity to cows, he often sees cow-related patterns in everyday objects. For example, if he looks at the string "bqessiyexbesszieb", Farmer John's eyes ignore some of the letters and all he sees is "bessiebessie".

Given a string s, let B(s)represent the maximum number of repeated copies of "bessie" one can form by deleting zero or more of the characters from s. In the example above, B("bqessiyexbesszieb")=2. Furthermore, given a string t, let A(t)
represent the sum of B(s)over all contiguous substrings s of t.

Farmer John has a string t of length at most 2⋅10⁵consisting only of characters a-z. Please compute A(t), and how A(t) would change after U(1≤U≤2⋅105) updates, each changing a character of t. Updates are cumulative.

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

The first line of input contains t.

The next line contains U, followed by U lines each containing a position p
(1≤p≤N) and a character c in the range a-z, meaning that the pth character of t
is changed to c.

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

Output U+1 lines, the total number of bessies that can be made across all substrings of t before any updates and after each update.

SAMPLE INPUT:

bessiebessie
3
3 l
7 s
3 s

SAMPLE OUTPUT:

14
7
1
7
Before any updates, twelve substrings contain exactly 1 "bessie" and 1 string contains exactly 2 "bessie"s, so the total number of bessies is 12⋅1+1⋅2=14.

After one update, t is "belsiebessie." Seven substrings contain exactly one "bessie."

After two updates, t is "belsiesessie." Only the entire string contains "bessie."

SCORING:

Input 2: |t|,U≤300
Inputs 3-5: U≤10
Inputs 6-13: |t|,U≤105
Inputs 14-21: No additional constraints.
Problem credits: Brandon Wang and Benjamin Qi