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 vertices of the tree. It is guaranteed → Virtual participation 
that the subgraph induced by the occupied vertices is connected.
Virtual contest is a way to take part in past
Initially, the slime occupies vertices s1 , s2 , … , sm . contest, as close as possible to participation
on time. It is supported only ICPC mode for
virtual contests. If you've seen these
First, we define a function f on a sequence of vertices. Consider a sequence a1 , a2 , … , ak . There are k pieces of food. For problems, a virtual contest is not for you -
solve these problems in the archive. If you
each i , the i -th piece of food is located at vertex ai . At first, only the first piece of food appears.
just want to solve some problem from a
contest, a virtual contest is not for you -
The slime may perform the following operations any number of times: solve this problem in the archive. Never use
someone else's code, read the tutorials or
communicate with other person during a
Move. The slime removes itself from one currently occupied vertex and expands to one currently unoccupied vertex. virtual contest.
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 by S must still be connected.
Start virtual contest

Eat. If the i -th piece of food has appeared and the slime currently occupies vertex ai , 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 → Problem tags
vertices.
data structures greedy trees
Define f ([a1 , a2 , … , ak ]) as the minimum number of Move operations needed for the slime to eat all k pieces of food in No tag edit access
order, starting from the initial occupied vertices s1 , s2 , … , sm .

There are q queries. The input is forced online. The input gives encoded values p1 , p2 , … , pq . Let ans0 = 0 . For each → Contest materials
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 ]) .
Announcement (en)

Tutorial (en)
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
4
≤ t ≤ 10 ). The description of the
test cases follows.

The first line of each test case contains three integers n, m, and q (2 ≤ m ≤ n ≤ 105 , 1 ≤ q ≤ 10
5
) — 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/20/2026 14:14:55UTC-6 (h1).
Desktop version, switch to mobile version.
Privacy Policy | Terms and Conditions

Supported by