AT_scpc2026_div2_k Cosmic Playground

#### 表示言語 / / While exploring the galaxy, Navi and Hyeongtae discovered a cosmic playground! The cosmic playground consists of $ N $ points and $ N-1 $ bidirectional passages. Each point in the cosmic playground is numbered from $ 1 $ to $ N $ . The $ i $ th passage connects points $ u_i $ and $ v_i $ in both directions. It is always possible to travel between any two distinct points using only the passages. In other words, the cosmic playground has a tree structure. Each point is connected to a single slide. For a permutation $ P=[P_1, P_2, \dots, P_N] $ of length $ N $ , sliding down the slide at point $ i $ moves you to point $ P_i $ . Navi wants to slide down the slides non-stop to enjoy the thrill of speed. On the other hand, Hyeongtae is worried that if Navi travels too far, Navi might get lost in space. After much deliberation, Navi and Hyeongtae defined the **risk level** $ f(r) $ of point $ r $ as follows: - The **distance** between points $ a $ and $ b $ is the minimum number of passages one must traverse to reach point $ b $ from point $ a $ using only the passages. - Navi starts at point $ s $ and continues moving using only slides, while Hyeongtae watches Navi from point $ r $ . The maximum distance between point $ r $ and any point Navi can reach is defined as the **maximum distance** $ d(r, s) $ . - The **risk level** $ f(r) $ when Hyeongtae remains at point $ r $ is the sum of the maximum distances $ \sum\limits_{s = 1}^{N}{d(r, s)} $ when Navi starts from each point. Hyeongtae wants to stay at the point where the risk level is minimized. Let us help Hyeongtae by calculating the risk level for each point. What is a permutation? A **permutation** of length $ N $ is a sequence that contains exactly one of each integer from $ 1 $ to $ N $ . For example, $ [2,1,4,3] $ is a permutation, but $ [4, 2, 1, 1] $ and $ [1, 2, 3, 5] $ are not.

The input is given from Standard Input in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \dots $ $ P_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

Output $ N $ integers $ f(1), f(2), \dots, f(N) $ , separated by spaces, where each integer represents the risk level of each point.

### Constraints - $ 3 \le N \le 100\,000 $ - $ 1 \le u_i < v_i \le N $ - The given graph is a tree. - $ P $ is a permutation. - All input values are integers.