Enter | Register
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Order Capital Round 2
H. Slime and Queries (Codeforces Round 1104, Div. 1 +
Div. 2)
time limit per test: 5 seconds
Finished
memory limit per test: 1024 megabytes
You are given a tree with n vertices numbered from 1 to n. A slime occupies exactly m → Virtual participation
vertices of the tree. It is guaranteed that the subgraph induced by the occupied vertices is
connected. Virtual contest is a way to take part in past
contest, as close as possible to participation
on time. It is supported only ICPC mode for
Initially, the slime occupies vertices s1 , s2 , … , sm . virtual contests. If you've seen these
problems, a virtual contest is not for you -
solve these problems in the archive. If you
First, we define a function f on a sequence of vertices. Consider a sequence a1 , a2 , … , ak . just want to solve some problem from a
There are k pieces of food. For each i , the i -th piece of food is located at vertex ai . At first, contest, a virtual contest is not for you -
solve this problem in the archive. Never use
only the first piece of food appears. someone else's code, read the tutorials or
communicate with other person during a
The slime may perform the following operations any number of times: virtual contest.
Move. The slime removes itself from one currently occupied vertex and expands to one Start virtual contest
currently unoccupied vertex.
Formally, let S be the current set of occupied vertices. Choose a vertex u ∈ S and a
vertex v ∉ S , and replace S with (S ∖ u) ∪ v. After the operation, the subgraph induced → Problem tags
by S must still be connected.
data structures greedy trees
Eat. If the i -th piece of food has appeared and the slime currently occupies vertex ai , No tag edit access
then the slime may eat the i -th piece of food. If 1 ≤ i < k, the (i + 1)-th piece of food
appears immediately after that. Eating does not change the occupied vertices. → Contest materials
Define f ([a1 , a2 , … , ak ]) as the minimum number of Move operations needed for the slime Announcement (en)
to eat all k pieces of food in order, starting from the initial occupied vertices s1 , s2 , … , sm .
Tutorial (en)
There are q queries. The input is forced online. The input gives encoded values
p1 , p2 , … , pq . Let ans0 = 0 . For each i = 1, 2, … , q, the actual vertex of the i -th query
is ci = ((pi − 1 + ansi−1 ) mod n) + 1 , where ansi = f ([c1 , c2 , … , ci ]) .
For each i = 1, 2, … , q , output ansi .
Input
Each test contains multiple test cases. The first line contains the number of test cases t (
1 ≤ t ≤ 10
4
). The description of the test cases follows.
The first line of each test case contains three integers n, m, and q (2
5
≤ m ≤ n ≤ 10 ,
5
1 ≤ q ≤ 10 ) — the number of vertices in the tree, the number of vertices occupied by the
slime, and the number of queries.
Each of the next n − 1 lines contains two integers u and v (1 ,
≤ u, v ≤ n u ≠ v ), denoting
an edge of the tree.
The next line contains m distinct integers s1 , s2 , … , sm (1 ≤ si ≤ n ) — the vertices
initially occupied by the slime. It is guaranteed that these vertices induce a connected
subgraph.
The next line contains q integers p1 , p2 , … , pq (1 ≤ pi ≤ n ) — the encoded query
vertices.
It is guaranteed that the sum of n over all test cases does not exceed 105 .
5
It is guaranteed that the sum of q over all test cases does not exceed 10 .
Output
For each test case, output q integers. The i -th integer should be ansi .
Example
input Copy
10
5 2 3
3 5
2 1
4 3
3 2
1 2
1 4 3
6 3 4
5 1
1 3
6 1
4 1
2 1
1 2 3
5 2 5 6
7 3 5
3 7
4 2
1 3
2 1
6 3
5 2
1 2 4
7 3 2 5 2
5 2 5
3 1
1 5
2 1
4 1
1 2
3 3 3 4 2
6 3 6
4 6
3 2
1 2
5 4
2 4
2 4 5
6 6 1 2 4 6
7 4 5
5 2
3 1
2 1
3 7
6 3
4 2
1 2 3 4
7 4 4 5 1
4 3 4
3 1
1 4
2 1
1 2 3
4 1 2 3
6 2 5
2 4
5 4
2 1
6 4
3 2
1 2
6 1 1 1 2
7 2 5
2 4
7 3
3 6
1 3
1 2
5 2
1 2
4 6 1 6 5
8 4 6
5 2
3 2
7 5
4 3
8 7
1 2
6 5
2 3 4 5
8 7 3 3 7 8
output Copy
0 2 3
1 1 2 3
2 4 6 8 9
1 2 3 4 4
1 2 3 4 4 4
1 2 3 3 4
1 1 2 2
2 4 6 8 9
1 4 7 10 11
2 3 4 4 5 5
Note
In the explanations below, the underlined vertex is the newly occupied vertex after a Move,
and vertices where the slime eats food are written in bold.
In the first test case, after decoding, the food appears at vertices 1, 4, 5 in order. Initially, the
slime occupies [1, 2].
1. For [1] , the slime already occupies vertex 1, so ans1 = 0 .
2. For [1, 4], one optimal process is [1, 2] → [2, 3] → [3, 4] , so ans2 = 2 .
– –
–
3. For [1, 4, 5], one optimal process is [1, 2] → [2, 3] → [3, 4] → [3, 5], so ans3 = 3 .
– –
– –
–
In the second test case, after decoding, the food appears at vertices 5, 3, 6, 2 in order.
Initially, the slime occupies [1, 2, 3].
1. For [5] , one optimal process is [1, 2, 3] → [1, 3, 5 ] , so ans1 = 1 .
–
–
2. For [5, 3], the same process also lets the slime eat at vertex 3, so ans2 = 1 .
3. For [5, 3, 6], one optimal process is [1, 2, 3] → [1, 3, 5 ] → [1, 3, 6 ] , so ans3 = 2 .
–
– –
–
4. For [5, 3, 6, 2] , one optimal process is [1, 2, 3] → [1, 3, 5 ] → [1, 3, 6 ] → [1, 2 , 3] , so
–
– –
– –
–
ans4 = 3 .
In the third test case, after decoding, the food appears at vertices 7, 5, 6, 4, 3 in order.
Initially, the slime occupies [1, 2, 4].
1. For [7] , one optimal process is [1, 2, 4] → [1, 2, 3] → [1, 3, 7 ] , so ans1 = 2 .
– –
–
2. For [7, 5], one optimal process is
[1, 2, 4] → [1, 2, 3] → [1, 3, 7 ] → [1, 2, 3] → [1, 2, 5 ] , so ans2 = 4 .
– –
– – –
–
3. For [7, 5, 6], one optimal process is
[1, 2, 4] → [1, 2, 3] → [1, 3, 7 ] → [1, 2, 3] → [1, 2, 5 ] → [1, 2, 3] → [1, 3, 6 ] , so
– –
– – –
– – –
–
ans3 = 6 .
4. For [7, 5, 6, 4] , continue with [1, 3, 6] → [1, 2, 3] → [1, 2, 4 ] , so ans4 = 8 .
– –
–
5. For [7, 5, 6, 4, 3], continue with [1, 2, 4] → [1, 2, 3 ] , so ans5 = 9 .
–
–
In the fourth test case, after decoding, the food appears at vertices 3, 4, 5, 2, 1 .
In the fifth test case, after decoding, the food appears at vertices 6, 1, 3, 5, 2, 4.
In the sixth test case, after decoding, the food appears at vertices 7, 5, 6, 1, 4 .
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jun/23/2026 12:50:18UTC+5.5 (i1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions
Supported by