时空限制

1S/512M

题目描述

给定一颗有 $n$ 个结点的树，每条树边都有颜色。树上的第 $i$ 条边连接结点 $u_i$ 和 $v_i$，颜色为 $c_i$。

定义图上任意两点的颜色值 $f(x,y)$ 为结点 $x$ 到结点 $y$ 路径上所有不同颜色的乘积，若 $x$ 与 $y$ 不连通或 $x=y$ 则 $f(x,y)=1$。形式化地：

$$f(x,y)=\begin{cases} \prod_{c\in C_{x,y}}c, & x \text{ 与 } y \text{ 连通时} \\ 1, & x \text{ 与 } y \text{ 不连通时} \end{cases}$$

其中 $C_{x,y}$ 表示从 $x$ 到 $y$ 的路径上所有颜色的集合， $x=y$ 时定义 $C_{x,y}=\{1\}$。

定义一张图的颜色值为 $\prod_{x = 1}^{n} \prod _{y = x}^{n}f(x,y)$ 。现在有 $n-1$ 次删边操作，请你在第一次操作前与每一次操作后输出此时图的颜色值，答案对 $998244353$ 取模。

在本题中，每一次删边操作都是持久化的，即已经删掉的边之后不会出现。

格式

输入格式

第一行包含一个整数 $n$，表示树的结点数量。

第 $2\sim n$ 行每行三个正整数 $u_i,v_i,c_i$，第 $i+1$ 行表示第 $i$ 条边连接 $u_i$ 和 $v_i$，颜色为 $c_i$。

第 $n+1$ 行 $n-1$ 个正整数 $x_1,x_2,\cdots,x_{n-1}$，$x_i$ 表示第 $i$ 次操作删除第 $x_i$ 条边。

输出格式

输出一行 $n$ 个整数，第一个整数表示操作前图的颜色值，第 $2\sim n$ 个整数分别表示第 $1\sim n-1$ 个操作后图的颜色值。

样例

样例输入 #1

5
1 2 2
1 3 3
2 4 4
2 5 5
4 2 1 3

样例输出 #1

829440000 27648 64 4 1

样例输入 #2

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

样例输出 #2

875954725 651482729 626967166 671006960 14400 1800 300 3 3 1

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	$n=$	分值	依赖子任务
$1$	$100$	$10$
$2$	$2000$	$20$	$1$
$3$	$10^5$	$70$	$1,2$

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le c_i\le 10$，保证图为树，保证 $x$ 是长度为 $n-1$ 的排列。