Problem Description

ckw has an unrooted tree. ckw will randomly pick a node and then start a random walk. In each unit of time, they move with equal probability to any node whose distance from the current node is at most $2$. Some nodes on the tree are marked. Find the expected time for ckw to reach a marked node for the first time.

Input Format

The first line contains two integers $n$, $m$, representing the number of nodes and the number of marks.

The next $n - 1$ lines each contain two integers $x$, $y$, indicating that there is an edge between $x$ and $y$.

The next $m$ lines each contain one integer, representing a marked node (duplicates may appear).

Output Format

Output $n$ lines, one number per line. The number on line $i$ is the expected number of steps when starting the random walk from node $i$, taken modulo $998244353$.

2 1
1 2
1

0
2

10 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
2
5

3
0
3
4
0
8
10
13
14
15

10 2
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9  
1 10
3
6

5
5
0
5
5
0
5
5
5
5

Hint

Constraints: $2 \le n \le 10^5$, $1 \le m \le n$.

Subtask 1 (20 pts): $n \le 300$.

Subtask 2 (16 pts): The $i$-th edge connects $i$ and $i + 1$.

Subtask 3 (8 pts): The $i$-th edge connects $1$ and $i + 1$.

Subtask 4 (20 pts): $n \le 3000$, and the maximum degree of any node is at most $4$.

Subtask 5 (36 pts): No additional constraints.

Translated by ChatGPT 5