Page Contents

**April Lunchtime 2021**

**A Special Tree SPTREE Solution**

You are given a tree with N nodes (numbered 1 through N). There are K special nodes f1,f2,…,fK in this tree.

We define d(p,q) to be the number of edges on the unique path from node p to node q.

You are given a node a. For each node b from 1 to N, find the maximum value of d(a,u)−d(b,u) where u is a special node, as well as any special node u for which that maximum value is attained.

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains three space-separated integers N, K, a.

The second line contains K space-separated integers f1,f2,…,fK.

N−1 lines follow. For each valid i, the i-th of these lines contains two space-separated integers ui and vi denoting an edge of the tree.

Output

For each test case, print two lines.

In the first line print N space-separated integers. For each valid i, the i-th integer should be the maximum value of d(a,u)−d(i,u) where u is a special node.

In the second line print N space-separated integers. For each valid i, the i-th integer should be any special node u for which the maximum of d(a,u)−d(i,u) is attained.

Constraints

1≤T≤200

1≤K≤N≤2⋅105

1≤a≤N

1≤fi≤N for each valid i

fi≠fj for each valid i and j such that i≠j

1≤ui,vi≤N for each valid i

the graph described on the input is a tree

the sum of N over all test cases does not exceed 4⋅105

Subtasks

Subtask #1 (10 points):

T≤11

N≤200

the sum of N over all test cases does not exceed 400

Subtask #2 (20 points):

T≤51

N≤2000

the sum of N over all test cases does not exceed 4000

Subtask #3 (30 points):

It holds that ui=i, vi=i+1 for each valid i.

Subtask #4 (40 points): original constraints

Sample Input

2

5 1 3

2

1 2

1 3

2 4

2 5

8 3 2

6 5 8

1 2

2 3

2 4

2 5

4 6

5 7

5 8

Sample Output

1 2 0 1 1

2 2 2 2 2

-1 0 -1 1 1 2 0 2

5 5 5 6 5 6 5 8

Explanation

Example case 1: The following picture shows the tree in the first example case with special nodes in bold:

The only special node is the node 2 and a=3. Therefore, the desired maximum is d(a,2)−d(b,2)=d(3,2)−d(b,2)=2−d(b,2) for each node b and it is always attained for the special node u=2.

Example case 2: The following picture shows the tree in the second example case with special nodes bolded:

The special nodes are 6, 5 and 8, and a=2. The maximum values of d(a,u)−d(b,u) (u being a special node) for each b are as follows:

- b=1: The maximum value of d(2,u)−d(1,u) is −1 and it is achieved for u=5 since d(2,5)−d(1,5)=1−2=−1.
- b=2: The maximum value of d(2,u)−d(2,u) is 0 and it is achieved for u=5 since d(2,5)−d(2,5)=1−1=0.
- b=3: The maximum value of d(2,u)−d(3,u) is −1 and it is achieved for u=5 since d(2,5)−d(3,5)=1−2=−1.
- b=4: The maximum value of d(2,u)−d(4,u) is 1 and it is achieved for u=6 since d(2,6)−d(4,6)=2−1=1.
- b=5: The maximum value of d(2,u)−d(5,u) is 1 and it is achieved for u=5 since d(2,5)−d(5,5)=1−0=1.
- b=6: The maximum value of d(2,u)−d(6,u) is 2 and it is achieved for u=6 since d(2,6)−d(6,6)=2−0=2.
- b=7: The maximum value of d(2,u)−d(7,u) is 0 and it is achieved for u=5 since d(2,5)−d(7,5)=1−1=0.
- b=8: The maximum value of d(2,u)−d(8,u) is 2 and it is achieved for u=8 since d(2,8)−d(8,8)=2−0=2.

*April Long Challenge 2021 Solutions*

*April Long Challenge 2021 Solutions*

- Chef and Dice SDICE Solution
- Worthy Matrix KAVGMAT Solution
- Binary String MEX MEXSTR Solution
- Boolean Game BOOLGAME Solution
- Tree Permutations TREEPERM Solution
- Destroy the EMP Chip CHAOSEMP Solution
- Chef and Pair Flips PAIRFLIP Solution
- String Power STRPOW Solution
- Brahma and Shiva SHRINES Solution
- Water Sort Puzzle (Challenge) WTRSORT Solution
- World Record BOLT Solution
- Strong Language SSCRIPT Solution
- Valid Pair SOCKS1 Solution

*Codechef Long Challenge Solutions*

*Codechef Long Challenge Solutions*

*February Long Challenge 2021*

*February Long Challenge 2021*

#### 1. Frog Sort Solution Codechef

#### 2. Chef and Meetings Solution Codechef

#### 3. Maximise Function Solution Codechef

#### 4. Highest Divisor Solution Codechef

#### 5. Cut the Cake Challenge Solution Codechef

#### 6. Dream and the Multiverse Solution Codechef

#### 7. Cell Shell Solution Codechef

#### 8. Multiple Games Solution Codechef

#### 9. Another Tree with Number Theory Solution Codechef

#### 10. XOR Sums Solution Codechef

#### 11. Prime Game Solution CodeChef

#### 12. Team Name Solution Codechef

### January Long Challenge 2021

**Chef and Division 3 DIVTHREE SOLUTION Code Chef****Encoded String DECODEIT SOLUTION Code Chef****Point Of Impact BILLRD SOLUTION Code Chef****Fair Elections FAIRELCT SOLUTION Code Chef****Watching CPL WIPL SOLUTION Code Chef****Chef and Ants ANTSCHEF SOLUTION Code Chef****Blackjack BLKJK SOLUTION Code Chef****And-Or Game ORAND SOLUTION Code Chef****Stack-Queue Sort (Challenge) SQSORT SOLUTION Code Chef****Expected Number of SCCs RCTEXSCC SOLUTION Code Chef****Curious Matrix CURMAT SOLUTION Code Chef****Cool Subsets COOLSBST SOLUTION Code Chef****Sequence Creation ARCRT SOLUTION Code Chef****Greedy Students GRDSTD SOLUTION Code Chef**

### November Challenge 2020 SOLUTION CodeChef

- Ada and Dishes SOLUTION ADADISH
- Iron Magnet and Wall SOLUTION FEMA2
- Magical Candy Store SOLUTION CNDYGAME
- Unusual Queries SOLUTION UNSQUERS
- Red-Black Boolean Expression SOLUTION RB2CNF
- Chef and the Combination Lock SOLUTION CHEFSSM
- Scalar Product Tree SOLUTION SCALSUM
- Connect on a Grid (Challenge) SOLUTION CONGRID

### October Lunchtime 2020 CodeChef SOLUTIONS

- AND Plus OR SOLUTION ANDOR
- Chef and Subtree MEXs SOLUTION SUBMEXS
- Chef Likes Good Sequences SOLUTION GSUB
- Cute Chef Gift SOLUTION COPAR
- Chef Is Just Throwing Random Words SOLUTION SSO
- Counting Spaghetti SOLUTION CDSUMS
- Chef and Edge Flipping SOLUTION EFLIP

*RELATED :*

- Top Best Keylogger in Python 3 Make One
*What is Hacking?**Secrets of the Deep Dark Web**CODECHEF September Lunchtime 2020 SOLUTIONS**August Lunchtime 2020 SOLUTIONS*

*Related :*

*A. Shandom Ruffle SOLUTION**B. Pear TreaP SOLUTION**C. Sneetches and Speeches 3 SOLUTION**D. The Grim Treaper SOLUTION**Y. Sneetches and Speeches 1 SOLUTION**Z. Trick or Treap SOLUTION**A. Floor Number SOLUTION CODE FORCES**B. Symmetric Matrix SOLUTION CODE FORCES**C. Increase and Copy SOLUTION CODE FORCES**D. Non-zero Segments SOLUTION CODE FORCES**E. Rock, Paper, Scissors SOLUTION CODE FORCES**F. Number of Subsequences SOLUTION CODE FORCES*

*Related :*

*Chef and Easy Queries SOLUTIONS CHEFEZQ**Covid Run SOLUTIONS CVDRUN OCTOBER CHALLENGE**Positive AND SOLUTIONS POSAND**Replace for X SOLUTIONS REPLESX**Village Road Network SOLUTIONS VILLNET**Random Knapsack SOLUTIONS RANDKNAP**D-Dimensional MST SOLUTIONS DDIMMST**Compress all Subsegments SOLUTIONS SEGCOMPR**Adding Squares SOLUTIONS ADDSQURE**Inversions SOLUTIONS INVSMOD2 OCOTBER CHALLENGE**Rooted Minimum Spanning Tree SOLUTIONS ROOTMST*