CF2277F Token Re-Moving

你有一棵包含 $n$ 个节点的树，节点编号从 $1$ 到 $n$。最开始，第 $i$ 个节点上有 $a_i$ 枚代币。 假设树以某个节点 $r$ 为根。对于节点 $u$，一次操作会将当前位于 $u$ 的子树 $^{\text{∗}}$ 内的所有代币全部移动到节点 $u$ 上。这次操作的代价是操作后节点 $u$ 上的总代币数量。 你还得到了一个 $1$ 到 $n$ 的排列 $p_1, p_2, \ldots, p_n$。排列 $p$ 的权值定义为依次对节点 $p_1, p_2, \ldots, p_n$ 进行上述操作时，所有操作总代价之和。 对于每个 $r$ 从 $1$ 到 $n$，求出以 $r$ 为根时，按照排列 $p$ 进行操作的权值。每个 $r$ 的初始代币分布互不影响，均从初始状态开始。由于答案可能很大，你需要输出对 $998244353$ 取模后的结果。 $^{\text{∗}}$ 节点 $u$ 的子树是由 $u$、其所有子孙节点以及这些节点之间的所有边组成的子图。

每个测试包含多组测试数据。第一行包含整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示树的节点数。 接下来 $n-1$ 行，每行两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示节点 $u$ 和 $v$ 之间有一条边。保证这些边构成一棵树。 接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i < 998244353$），表示每个节点初始的代币数。 接下来一行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$，且互不相同），表示排列 $p$。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数，第 $r$ 个整数为以 $r$ 为根时的排列 $p$ 的权值，对 $998244353$ 取模。

在第一个测试用例中，考虑 $r=1$。初始代币为 $[1]$。对 $p_1=1$ 的操作将 $\{1\}$ 子树的所有代币移动到节点 $1$ 上，因此代价为 $1$。所以 $p$ 的权值为 $1$。 在第二个测试用例中，考虑 $r=1$。初始代币为 $[5, 13]$。 - 第一步对 $p_1=2$，将 $\{2\}$ 子树的所有代币移到 $2$，代价为 $13$，状态仍为 $[5, 13]$。 - 第二步对 $p_2=1$，将 $\{1, 2\}$ 子树的所有代币移到 $1$，代价为 $18$，此时状态变为 $[18, 0]$。 因此，$p$ 的权值为 $13 + 18 = 31$。 在第三个测试用例中，考虑 $r=1$。初始代币为 $[7, 2, 9]$。 - 第一步对 $p_1=2$，将 $\{2\}$ 子树的所有代币移到 $2$，代价为 $2$，状态不变。 - 第二步对 $p_2=3$，将 $\{3\}$ 子树的所有代币移到 $3$，代价为 $9$，状态不变。 - 第三步对 $p_3=1$，将 $\{1, 2, 3\}$ 子树的所有代币移到 $1$，代价为 $18$，此时状态变为 $[18, 0, 0]$。 所以，$p$ 的权值为 $2 + 9 + 18 = 29$。 由 ChatGPT 5 翻译