分类： 赛事资讯

USACO 很高兴地宣布 2025-2026 赛季的决赛入围者，全部受邀参加 2026 年 USACO 夏季训练营：

除了参加我们训练营并争夺代表美国参加 2026 年国际信息学奥林匹克竞赛的决赛入围者外，以下 EGOI 决赛入围者已受邀参加我们的训练营，其中一些 (*) 还被选为代表美国参加 2026 年欧洲女子信息学奥林匹克竞赛的代表队：

这些计算机科学预科学生因其在 2025-2026 赛季 USACO 比赛中的出色表现而被选中，他们代表了美国最强的算法问题解决者。请与我们一起祝贺这些人所取得的非凡成就！

美国公开赛是我们“全国锦标赛”的赛事。这是一项针对美国预科生的监督邀请赛，参赛者需在前三次月度比赛中表现最优异。

USACO 2026 年 美国公开赛

1 Arranging Cows
查看问题 | 测试数据 | 解决方案
2 Haybale Stacks
查看问题 | 测试数据 | 解决方案
3 Perfect Binary Trees
查看问题 | 测试数据 | 解决方案

结语

这是我们许久以来首次举办的监考竞赛。这是一次有益的经历，帮助我们为未来的监考竞赛优化细节。总体而言，我认为本次竞赛进行得相当顺利。本次竞赛的结果是我们选拔2026年USACO夏季训练营邀请对象的主要依据之一。

众多人士为本次USACO竞赛的质量与成功作出了贡献，包括Sujay Konda, Bing-Dong Liu, Benjamin Qi, Claire Zhang, Richard Qi, Botao Yuan, Thomas Liu, Avnith Vijayram, Alex Chen, and Brandon Wang。我们还非常感谢本赛季的赞助商——Citadel，感谢他们为我们的项目提供了所有支持！

编码愉快！

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

A perfect binary tree is a rooted tree where every non-leaf node has exactly two children and all leaf nodes are at an equal distance from the root.

An unrooted perfect binary tree is an unrooted tree that is a perfect binary tree when rooted at one of its nodes.

Bessie has a tree with N (1≤N≤10⁵) nodes. Determine the number of ways to remove a subset of edges from the tree so that the resulting forest is a collection of unrooted perfect binary trees. As the answer may be very large, output the result modulo 10⁹+7.

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

The first line contains an integer T (1≤T≤100), the number of independent test cases.

The first line of each test case contains an integer N.

Each of the next N−1 lines of each test case contains two integers u_i and v_i (1≤u_i ,v_i≤N) indicating an edge between nodes u_i and v_i .

It is guaranteed that for each test case, the given edges form a tree with N nodes.

Additionally, the sum of N over all test cases does not exceed 2⋅10⁵.

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

For each test case, output a single integer: the number of subsets of edges that, when removed, result in a forest that is a collection of unrooted perfect binary trees, modulo 10⁹+7.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

8
2
14

In the first test case, Bessie can remove any of the following subsets of edges to get a forest of perfect binary trees:

1.(2,6)(2,6)

2.(1,2)(1,2), (2,3)(2,3), (2,6)(2,6)

3.(1,2)(1,2), (2,3)(2,3), (4,6)(4,6)

4.(1,2)(1,2), (2,3)(2,3), (5,6)(5,6)

5.(1,2)(1,2), (4,6)(4,6), (5,6)(5,6)

6.(2,6)(2,6), (4,6)(4,6), (5,6)(5,6)

7.(2,3)(2,3), (4,6)(4,6), (5,6)(5,6)

8.(1,2)(1,2), (2,3)(2,3), (2,6)(2,6), (4,6)(4,6), (5,6)(5,6)

The first subset results in two subtrees of height 11, the last subset results in six subtrees of height 00, and the other subsets result in three subtrees of height 00 and one subtree of height 11.

SCORING:

Inputs 2-3: N≤15
Inputs 4-5: No node is adjacent to more than two other nodes.
Inputs 6-9: N≤1000, the sum of N does not exceed 20002000, and no node is adjacent to more than three other nodes.
Inputs 10-13: No node is adjacent to more than three other nodes.
Inputs 14-21: No additional constraints.

Problem credits: Avnith Vijayram

**Note: The time limit for this problem is 2.5s.**

Farmer John has N stacks of haybales (1≤N≤5⋅10⁵), where the ith stack contains a_i haybales (1≤a_i ≤10⁹ ). He wants to remove all of these haybales and has M (1≤M≤2500) cows available to help him. If hired, the ith cow will repeat the following s_i times (1≤s_i≤100) for a cost of c_i (1≤c_i≤10⁹):

If the stack contains at least p_i haybales (1≤p_i≤10⁹), then the cow will remove one haybale.

If the stack contains less than p_i haybales, the cow does nothing.

For each stack, FJ wants to remove all of the haybales in it. He will do this by hiring cows in sequence (possibly the same cow more than once) until the stack becomes empty. Help FJ determine for each stack the minimum cost to empty it.

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

The first line contains T (1≤T≤100), the number of independent tests. Each test is formatted as follows:

The first line contains an integer N. The second line contains N integers,a₁,a₂,…,a_N.

The third line contains an integer M. Then the next M lines will contain p_i,s_i,c_i.

It is guaranteed that the cows will be able to remove all the haybales in every stack. Additionally, it is guaranteed that the sum of N over all tests does not exceed 5⋅10⁵, and the sum of M over all tests does not exceed 2500.

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

For each test, print N space-separated integers, the ith integer being the cost of removing all the haybales in the ith stack.

SAMPLE INPUT:

2
3
15 100 10
4
101 1 1
1 4 8
9 3 5
15 2 3
3
15 100 10
4
101 1 1
1 1 5
9 1 8
15 1 3

SAMPLE OUTPUT:

29 155 21
73 328 50

First test: For the last stack of initial size 1010, we can hire cow 33 once, which costs 55 and will remove haybales twice (not thrice because the number of haybales turns to 88 after the second one is removed). Then we can hire cow 22 twice, removing the 88 haybales, resulting in no haybales left. The total cost is 5+8+8=215+8+8=21.

Second test: This satisfies max(s)=1.

SCORING:

Inputs 2-3: a_i≤100
Inputs 4-5: max(s)=1
Inputs 6-9: max(s)≤4
Inputs 10-15: max(s)≤20
Inputs 16-21: No additional constraints.

Problem credits: Sujay Konda

You are given a length-N bitstring s_1…N(2≤N≤10⁹). In one operation, you can reverse a range s_l…r if the following conditions are true:

1.The size of the range is even.

2.The first half of the range consists of one character (either 00 or 11), and the second half contains the opposite character

3.Either l=1 or sl−1≠sl

4.Either r=N or  s_r+1≠sr

Find the minimum number of operations to move all of the 11s to the front, or report that it is impossible. If it is possible to do so, also output the number of sequences of operations achieving this minimum, modulo 10⁹+7.

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

The first line contains T (1≤T≤2026), the number of independent tests. Each test is specified in the following format:

The bitstring is given in a compressed format. The first line contains R, the number of runs in the string (2≤R≤800), and the first character of the string (either 0 or 1).

The next line contains R space-separated integers l₁,l₂,l₃,…l_R  (0<l_i<10⁹), the lengths of maximal consecutive blocks of equal characters in s. It's guaranteed that N=

Additionally, it is guaranteed that the sum of  R² over all tests does not exceed 1.5⋅10⁶.

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

For each test case, print the minimum number of operations to move all of the 11s to the front or −1−1 if it is impossible, as well as the number of sequences of operations achieving this minimum modulo 10⁹+7.

SAMPLE INPUT:

9
2 0
1 1
2 1
1 1
2 1
2 1
2 0
1 2
5 0
1 1 1 2 1
3 0
1 2 1
8 0
1 1 2 1 1 2 1 1
6 0
3 3 1 2 2 1
7 0
5 1 1 3 2 1 1

SAMPLE OUTPUT:

1 1
0 1
0 1
-1 0
2 1
-1 0
4 7
3 1
4 1

Here is the sequence of two operations for the fifth testcase: 010110→100110→111000.010110→100110→111000.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0 1
1 1
2 1
3 3
4 9

In all of these test cases, the minimum number of operations equals R/2−1.

Here are all three possible sequences of three operations for the fourth test case:

(1)
10101010
-> 11001010
-> 11001100
-> 11110000

(2)
10101010
-> 10110010
-> 10001110
-> 11110000

(3)
10101010
-> 10101100
-> 11001100
-> 11110000

SCORING:

Input 3: N≤10, all tests are distinct
Input 4: R≤10
Inputs 5-8: R≤100, the sum of R² over all tests does not exceed 10⁵, the minimum number of operations is guaranteed to equal R/2−1.
Inputs 9-12: R≤100, the sum of R² over all tests does not exceed 10⁵.
Inputs 13-16: No additional constraints.

Problem credits: Sujay Konda