CF2237H Slime and Queries

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 that the subgraph induced by the occupied vertices is connected. Initially, the slime occupies vertices $ s_1,s_2,\ldots,s_m $ . First, we define a function $ f $ on a sequence of vertices. Consider a sequence $ a_1,a_2,\ldots,a_k $ . There are $ k $ pieces of food. For each $ i $ , the $ i $ -th piece of food is located at vertex $ a_i $ . At first, only the first piece of food appears. The slime may perform the following operations any number of times: - Move. The slime removes itself from one currently occupied vertex and expands to one currently unoccupied vertex.Formally, let $ S $ be the current set of occupied vertices. Choose a vertex $ u\in S $ and a vertex $ v\notin S $ , and replace $ S $ with $ (S\setminus{u})\cup{v} $ . After the operation, the subgraph induced by $ S $ must still be connected. - Eat. If the $ i $ -th piece of food has appeared and the slime currently occupies vertex $ a_i $ , then the slime may eat the $ i $ -th piece of food. If $ 1\le i \lt k $ , the $ (i+1) $ -th piece of food appears immediately after that. Eating does not change the occupied vertices. Define $ f([a_1,a_2,\ldots,a_k]) $ as the minimum number of Move operations needed for the slime to eat all $ k $ pieces of food in order, starting from the initial occupied vertices $ s_1,s_2,\ldots,s_m $ . There are $ q $ queries. The input is forced online. The input gives encoded values $ p_1,p_2,\ldots,p_q $ . Let $ \mathrm{ans}_0=0 $ . For each $ i=1,2,\ldots,q $ , the actual vertex of the $ i $ -th query is $ c_i=((p_i-1+\mathrm{ans}_{i-1}) \bmod n)+1 $ , where $ \mathrm{ans}_i=f([c_1,c_2,\ldots,c_i]) $ . For each $ i=1,2,\ldots,q $ , output $ \mathrm{ans}_i $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains three integers $ n $ , $ m $ , and $ q $ ( $ 2\le m\le n\le 10^5 $ , $ 1\le q\le 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\le u,v\le n $ , $ u\ne v $ ), denoting an edge of the tree. The next line contains $ m $ distinct integers $ s_1,s_2,\ldots,s_m $ ( $ 1\le s_i\le n $ ) — the vertices initially occupied by the slime. It is guaranteed that these vertices induce a connected subgraph. The next line contains $ q $ integers $ p_1,p_2,\ldots,p_q $ ( $ 1\le p_i\le n $ ) — the encoded query vertices. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ . It is guaranteed that the sum of $ q $ over all test cases does not exceed $ 10^5 $ .

For each test case, output $ q $ integers. The $ i $ -th integer should be $ \mathrm{ans}_i $ .

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 $ \mathbf{1} $ , so $ \mathrm{ans}_1=0 $ . 2. For $ [1,4] $ , one optimal process is $ [\mathbf{1},2]\to[2,\underline{3}]\to[3,\underline{\mathbf{4}}] $ , so $ \mathrm{ans}_2=2 $ . 3. For $ [1,4,5] $ , one optimal process is $ [\mathbf{1},2]\to[2,\underline{3}]\to[3,\underline{\mathbf{4}}]\to[3,\underline{\mathbf{5}}] $ , so $ \mathrm{ans}_3=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]\to[1,3,\underline{\mathbf{5}}] $ , so $ \mathrm{ans}_1=1 $ . 2. For $ [5,3] $ , the same process also lets the slime eat at vertex $ \mathbf{3} $ , so $ \mathrm{ans}_2=1 $ . 3. For $ [5,3,6] $ , one optimal process is $ [1,2,3]\to[1,3,\underline{\mathbf{5}}]\to[1,3,\underline{\mathbf{6}}] $ , so $ \mathrm{ans}_3=2 $ . 4. For $ [5,3,6,2] $ , one optimal process is $ [1,2,3]\to[1,3,\underline{\mathbf{5}}]\to[1,3,\underline{\mathbf{6}}]\to[1,\underline{\mathbf{2}},3] $ , so $ \mathrm{ans}_4=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]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}] $ , so $ \mathrm{ans}_1=2 $ . 2. For $ [7,5] $ , one optimal process is $ [1,2,4]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}]\to[1,\underline{2},3]\to[1,2,\underline{\mathbf{5}}] $ , so $ \mathrm{ans}_2=4 $ . 3. For $ [7,5,6] $ , one optimal process is $ [1,2,4]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}]\to[1,\underline{2},3]\to[1,2,\underline{\mathbf{5}}]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{6}}] $ , so $ \mathrm{ans}_3=6 $ . 4. For $ [7,5,6,4] $ , continue with $ [1,3,\mathbf{6}]\to[1,\underline{2},3]\to[1,2,\underline{\mathbf{4}}] $ , so $ \mathrm{ans}_4=8 $ . 5. For $ [7,5,6,4,3] $ , continue with $ [1,2,\mathbf{4}]\to[1,2,\underline{\mathbf{3}}] $ , so $ \mathrm{ans}_5=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 $ .