作者： chenchen

Suppose the function randint(l,r) returns an integer independently and uniformly at random from the range [l,r].

Bessie generates a random labeled tree on N vertices (2≤N≤2⋅10⁵) using the following two-step process:

1.Start with vertices labeled 1 through N. For each i from 2 to N, add an edge between vertex i and randint(1,i−1).

2.Choose a permutation p₁,p₂,…,p_N of {1,2,…,N} uniformly at random. Relabel every vertex v as p_v.

Now, Farmer John is looking at the edge set of the final tree and wants to know the probability that the two-step process above produces a tree with exactly this edge set. Can you determine this probability modulo 10⁹+7?

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

The input consists of T(1≤T≤10) independent inputs. Each input is specified as follows:

The first line contains N.

The next N−1 lines contain the edges of the tree specified by two space-separated integers u and v (1≤u,v≤N). It is guaranteed that these edges induce a tree.

It is guaranteed that the sum of N across all tests does not exceed 5⋅10⁵.

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

For each test, output the probability modulo 10⁹+7 on a new line (note that the output probability is a ratio of integers, so you will want to print the result of this division when working modulo 10⁹+7).

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1
333333336
83333334
55555556

The probabilities are 1, 1/3, 1/12, 1/18.

First test: There is only one tree on N=2 vertices, so the probability of generating it is just 1.

Second test: there are three trees on N=3 vertices, and each of them is equally likely to have been generated by the process above. And 1/3≡333333336(mod 10⁹+7).

SCORING:

Input 2-3: N≤8
Inputs 4-9: N≤2000
Inputs 10-21: No additional constraints.

Problem credits: Benjamin Qi

**Note: The time limit for this problem is 3s, 1.5x the default.**

Farmer John's farm structure can be represented as a connected undirected graph with N vertices and M unweighted edges (2≤N≤2⋅10⁵,N−1≤M≤2⋅10⁵
). Initially, Farmer John is at his barn, represented by farm 1.

Initially, farms s₁,s₂,…,s_K contain flower fields and farms d₁,d₂,…,d_L are destination farms. FJ calls a path pretty if:

It starts at farm 1.
It ends at some destination farm x.
There is no shorter path starting at farm 1and ending at farm x.
FJ visits all flower fields along the way.

FJ can wave his magic wand and make up to one more farm contain a flower field (if it doesn't already). However, FJ isn't very decisive. For farms f numbered 2 through N, after FJ temporarily makes farm f contain a flower field, determine if there exists a pretty path.

Note that there are multiple test cases, and each case must be treated independently.

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

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

The first line of each test case contains N, M, K, and L(0≤K≤N−1,1≤L≤N−1).

The following line contains s₁,s₂,…,s_K ( 2≤ s_i ≤N, siare all distinct ).

The following line contains d₁,d₂,…,d_L (2≤d_i≤N, d_i are all distinct).

The following M lines contain u and v, denoting there is an undirected edge between farms u and v. All edges are considered to have equal length. It is guaranteed that there aren't any multi-edges or self loops.

It is guaranteed that both the sum of N and the sum of M do not exceed 10⁶ over all test cases.

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

For each test case, output a binary string of length N−1. The i'th character in the string should be 1 if the answer holds true for the (i+1)'th farm.

SAMPLE INPUT:

1
7 7 0 1

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

SAMPLE OUTPUT:

111110

Since 5 is the only destination farm, the answer holds true if the i'th farm lies on any shortest path from 1 to 5.

There are two shortest paths from 1 to 5, which are 1→2→3→4→5 and 1→2→3→6→5.

Since there are no farms that already contain flower fields, the answer for farm i
holds true if farm i lies on at least one of the two aforementioned paths.

SAMPLE INPUT:

1
6 6 0 2

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

SAMPLE OUTPUT:

11010

There are two destination farms: 5 and 3. Since there are no farms that already contain flower fields, the i'th farm must lie on a shortest path to either 5 or 3. Since farm 2 lies on a shortest path to farm 5, so the answer holds for farm 2. Trivially, farm 3 lies on the shortest path to farm 3 and farm 5 lies on the shortest path to farm 5.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

111
000
1011

For the first test case, the answer holds true for the i'th farm if FJ can pass through farm i, farm 2, and farm 3 (in no particular order) on some shortest path to farm 4. It can be shown that the answer holds true for all farms.

SCORING:

Inputs 4-6: K=0and L=1
Inputs 7-9: K=0
Inputs 10-23: No additional constraints

Problem credits: Chongtian Ma

USACO 2026赛季的第三场比赛涵盖了涵盖多种技术和难度的算法编程问题。

在为期四天的比赛期间，共有7302名不同用户登录了该活动。共有5084名参与者提交了至少一个解决方案，来自100+个不同国家。3203名参与者来自美国，中国、加拿大、韩国、马来西亚、印度和新加坡的参与度较高。

总共有14003份评分提交，按语言分类如下：

8997 C++17
2349 Python-3.6.9
1479 Java
1052 C++11
99 C
27 Python-2.7.17

以下是白金、金、银和铜三项比赛的详细成绩。 你还可以找到每个问题的解决方案和测试数据，点击任意 问题你可以练习在“分析模式”下重新提交解答。

USACO 2026年 第三场 比赛，白金奖

白金组共有300名参与者，其中243名是大学预科生。

1 All Pairs Shortest Paths
查看问题 | 测试数据 | 解决方案
2 Blast Damage
查看问题 | 测试数据 | 解决方案
3 Min Max Subarrays II
查看问题 | 测试数据 | 解决方案

USACO 2026年 第三场 比赛，金奖

金组共有1245名参与者，其中910名是大学预科生。所有在本比赛中得分达到750分或以上的选手将自动晋级白金组。

1 Good Cyclic Shifts
查看问题 | 测试数据 | 解决方案
2 Picking Flowers
查看问题 | 测试数据 | 解决方案
3 Random Tree Generation
查看问题 | 测试数据 | 解决方案

USACO 2026年 第三场 比赛，银奖

银组共有2446名参赛者，其中1916人为预科生。所有在本比赛中得分达到700分或以上的选手将自动晋级金组。

1 Clash!
查看问题 | 测试数据 | 解决方案
2 Milk Buckets
查看问题 | 测试数据 | 解决方案
3 Point Elimination
查看问题 | 测试数据 | 解决方案

USACO 2026年 第三场 比赛，铜奖

铜组共有3014名参赛者，其中2374人为大学预科生。所有在本比赛中得分达到700分或以上的选手将自动晋级银组。

1 Make All Distinct
查看问题 | 测试数据 | 解决方案
2 Strange Function
查看问题 | 测试数据 | 解决方案
3 Swap to Win
查看问题 | 测试数据 | 解决方案

结语

我对本季第三场也是最后一场“标准级”竞赛的结果感到满意。从技术层面看，一切进展非常顺利（我们在第二场竞赛中发现负载相关问题后对基础设施进行了升级，这些改进似乎取得了显著成效）。尽管本次竞赛的题目难度依然极高，但多个组别的大量选手均获得了晋级。我和USACO团队仍需投入超出理想时长的精力处理学术诚信相关事务（例如手动审核提交内容、向校方负责人提交报告等），但这些工作对于维持我们与他人所期待的竞赛高标准诚信至关重要。生成式人工智能加剧了这一挑战，但我们希望通过加强监考措施来缓解这一问题——我们期待本季最后一场邀请制监考竞赛能够顺利进行。

对于尚未晋级的选手，请记住：实践越多，你的算法编码能力就会越强——请坚持下去！USACO竞赛旨在挑战最顶尖的学生，要想脱颖而出需要付出大量努力。现在，你还可以通过"分析模式"重新提交解题方案，并从判题服务器获得反馈，以帮助修复代码中的错误。

For a permutation p₁,p₂,…,p_N of 1…N (1≤N≤2⋅10⁵), let f(p)=. A permutation is good if it can be turned into the identity permutation using at most f(p) swaps of adjacent elements.

Given a permutation, find which cyclic shifts of it are good.

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

The input consists of T (1≤T≤10⁵) independent tests. Each test is specified as follows:

The first line contains N.

The second line contains p₁,p₂,…,p_N (1≤p_i≤N), which is guaranteed to be a permutation of 1…N.

It is guaranteed that the sum of N over all tests does not exceed 10⁶ .

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

For each test, output two lines:

On the first line, output the number of good cyclic shifts k.

Then output a line with k space-separated integers s (0≤s<N) in increasing order, meaning that p is good when cyclically shifted to the right s times.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0

2
0 1
5
0 1 2 3 4

Consider the second test case, where p=[1,2,4,3].

f(p)=(|1−1|+|2−2|+|4−3|+|3−4|)/2=1. Since p can be turned into the identity permutation in one move by swapping p₃ and p₄, p is good.

Cyclically shifting p to the right 1 time, we get q=[3,1,2,4]. f(q)(|3−1|+|1−2|+|2−3|+|4−4|)/2=2. Since q can be turned into the identity permutation in two moves by swapping q₁ two steps forward, q is good.

It can be seen that the other two cyclic shifts are not good.

SCORING:

Input 2: N≤10
Inputs 3-5: T≤10,N≤2000
Inputs 6-11: No additional constraints.
Problem credits: Akshaj Arora

You are given integers N,Q (1≤N,Q≤2⋅105) and Q constraints represented by four integers ti,li,ri,ki (1≤ti≤2,1≤li≤ri≤N,0≤ki≤109,all ki are distinct).

Construct an array a consisting of N integers between 0 and 109 such that for all 1≤i≤Q, mina[li...ri]=ki if ti=1 and maxa[li...ri]=ki if ti=2. If multiple valid arrays exist, print any. If no valid array exists, print −1.

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

The first line contains an integer T (1≤T≤10⁴) representing the number of independent test cases.

For each test case, the first line contains two integers N,Q.

The next Q lines each contain 4 integers t_i l_i r_i k_i.

It is guaranteed that neither the sum of N nor the sum of Q over all test cases exceed 2⋅10⁵.

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

For each test case, if a valid array exists, output N space-separated integers a₁…a_N on a new line. Otherwise, print −1.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

-1
1 2
0 3 0 0

In the first test case, the answer is −1 because the minimum value of the array cannot be both 1 and 2 at the same time.

In the second test case, a[1...2] has a minimum of 1 at a[1] in the sample output, satisfying the first constraint. Since a[2]=2, the second constraint is also satisfied.

In the third test case, there are multiple solutions. For instance, the array [4,3,2,1]
would also be accepted.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

1 2
-1
3 3 0 2 2
1 5 2 6

In the second test case, the array [3,5,1] satisfies the first constraint but not the second constraint. Contrarily, the array [3,1,1] satisfies the second constraint but not the first constraint. It can be proven that no array can satisfy both constraints at the same time, hence the answer is −1.

For all other test cases, it can be proven that the constructed array satisfies all Q
constraints.

SCORING:

Inputs 3-4: N,Q≤100 and all t_i within the same test case are equal
Inputs 5-6: all t_i  within the same test case are equal
Inputs 7-10: N,Q≤100
Inputs 11-14: No additional constraints.

Problem credits: Charlie Yang

Bessie is playing a video game where she needs to defeat a line of N enemies with initial HPs given by the list v₁…v_N (1≤N≤2⋅10⁵,0≤v_i≤10⁹). In one attack, she can perform the following sequence of steps:

Choose i such that the ith enemy is still alive (that is, v_i>0).
Deal one damage to the ith enemy and all enemies adjacent to it that are still alive. Specifically, for each j∈[max(i−1,1),min(i+1,N)], if v_j>0, subtract one from v_j.

Help Bessie determine the minimum number of attacks she needs to defeat all enemies (that is, reduce all v_i to 0).

Additionally, you are given a parameter M (0≤M≤2). If M>0, please output a construction achieving the minimum number of attacks with a small number of runs, where a run consists of attacking the same enemy consecutively.

Let R be the number of runs in your construction. Your construction should be in the following format: output R on its own line, followed by R lines each containing two integers i and r (1≤i≤N,0≤r≤10⁹), meaning that Bessie attacks the i-th enemy r times consecutively.

Depending on the value of M, R must satisfy one of the following constraints:

M=1: R≤2N(it can be proven that a construction always exists).
M=2: R≤f(N), where f(N) is the maximum minimum number of runs over all lists of length N.

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

Each input consists of T (1≤T≤10⁵) independent tests. The first line contains T
and M.

Each test is specified as follows:

The first line contains N.

The second line contains v₁…v_N.

It is guaranteed that the sum of N over all tests does not exceed 10⁶ .

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

For each test, output the minimum number of attacks on the first line.

Then if M>0, output R+1 additional lines as specified above. Any valid construction will be accepted.

SAMPLE INPUT:

2 0
1
10
3
6 1 7

SAMPLE OUTPUT:

10
12

For the second test, you can first perform one attack on the middle enemy. Then, in any order after that, perform five attacks on the first enemy and six attacks on the last enemy.

SAMPLE INPUT:

2 1
1
10
3
6 1 7

SAMPLE OUTPUT:

10
2
1 0
1 10
12
4
2 1
1 5
3 2
3 4

This output receives credit because R=2≤2 for test 1 and R=4≤6 for test 2.

SAMPLE INPUT:

2 2
1
10
3
6 1 7

SAMPLE OUTPUT:

10
1
1 10
12
3
2 1
3 6
1 5

This output receives credit because R=1≤f(1) for test 1 and R=3≤f(3) for test 2.

SCORING:

Inputs 4-7: M=0
Inputs 8-11: M=1
Input 12-13: M=2
Problem credits: Benjamin Qi

You have a bunch of triangular regions that tessellate an infinite 2D plane. The tesselation is defined as follows (see the diagram for a better understanding):

Recall that Euler's formula states that e^ix=cos(x)+isin(x) for real x. First, draw a vertex at x+yexp(πi/3)on the complex plane for all integers x,y.

Then for every three vertices from the step above forming an equilateral triangle with side length 1, draw the edges forming its border. Additionally, draw a vertex at the center of the triangle and edges from the center of the triangle to each of three outer vertices.

You are given N (2≤N≤2⋅10⁵) input points, each of which lies strictly within some region (i.e., not on any vertex or edge). For any pair of the input points, define the distance between them to be the smallest number of edges crossed when drawing a path from one point to the other that doesn't pass through any vertex.

Output the sum of all N(N−1)/2 pairwise distances between the input points.

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

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

The first line contains N.

The next N lines each contain three integers x, y, and z(0≤x,y<10⁶,0≤z<12) representing a point at x+yexp(πi/3)+ϵ⋅exp((1+2z)πi/12) on the complex plane (ϵ
being a small positive number).

It is guaranteed that the sum of N over all tests doesn't exceed 2⋅10⁵.

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

For each test, output the sum of all N(N−1)/2 pairwise distances on a new line.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0
3
6
12
2
6

The second test is illustrated below:

The vertex at x+yexp(πi/3) is labeled with (x,y) for each x∈[−1,2],y∈[−1,2].

Dots are drawn at the vertices mentioned above as well as the vertices that are the centers of each equilateral triangle.

The triangular region containing (x,y,z)=(0,0,0) is highlighted in green.

The triangular region containing (x,y,z)=(1,1,7) is highlighted in blue. Note that 15π/12=225^∘.

An example path from the first region to the second crossing three edges is drawn.

SCORING:

Inputs 2-5: N≤10, 0≤x,y<5
Inputs 6-13: N≤10
Inputs 14-21: T=1
Problem credits: Benjamin Qi