P5637 ckw's Tree

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.

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 $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$.

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