P10894 Virtual Tree

First, you do not need to know anything about virtual trees to solve this problem. —Even though this is the first problem in the theme set whose name contains “virtual tree” (

Sister jq has a tree rooted at node $1$. Define that a non-empty subset $s$ of the node set $S$ of the tree is good if and only if it satisfies $\forall i,j \in s, \text{LCA}(i,j) \in s$. [What is $\text{LCA}$?](https://oi-wiki.org/graph/lca/) To make the shape of the tree cuter, Sister jq plans to prune (delete) a subtree rooted at some node $i$ (that is, in the original tree, delete node $i$ and all nodes in its subtree, and also delete all edges connected to them). She has several pruning plans but has never carried them out. You need to compute, after carrying out each plan, the number of good non-empty subsets of this tree. Since the answer may be very large, output it modulo $998244353$.

The first line contains an integer $n$ ($n \leq 5 \times 10^5$), which is the number of nodes in the tree. Lines $2$ to $n$ each contain two integers $u_i, v_i$, representing an edge connecting $u_i$ and $v_i$. Line $n+1$ contains an integer $m$ ($m \leq 5 \times 10^5$), which is the number of pruning plans. The next line contains $m$ integers $q_i$, meaning that the subtree rooted at $q_i$ will be pruned (deleted).

Output $m$ lines. On line $i$, output an integer $k$, which is the number of good non-empty subsets of the original tree after deleting the subtree rooted at $q_i$.

Explanation of Sample 1: After deleting the subtree rooted at $2$, all $3$ non-empty subsets of the remaining node set satisfy the property. After deleting the subtree rooted at $5$, among all $15$ non-empty subsets of the remaining node set, $\{3,4\}$ and $\{1,3,4\}$ do not satisfy the property. For the first $10\%$ of the testdata, $n, m \leq 20$. For the first $30\%$ of the testdata, $n, m \leq 3000$. For $100\%$ of the testdata, $1 \leq n, m \leq 5 \times 10^5$, $q \in [1,n]$. Translated by ChatGPT 5