题目描述

小猫梦见自己在游戏中对战。敌营是 $n$ 个结点，以 $1$ 为根的树，其中和恰好 $1$ 个结点相邻而不为根的点叫做叶子。

敌人会为每个叶子都设定了一个整数作为密码。要想破解敌方的防线，就要获取每个叶子的密码。

现在小猫可以用 $C_i$ 金币收买其第 $i$ 个结点，这个结点就会透露出其子树内所有叶子的密码之和。

小猫当然想用最少的金币来获取各叶子的密码啦!

现在请你回答以下问题中的前 $k$ 个:

【输入格式】

第一行 $n$ 个正整数。接下来一行 $n$ 个正整数， $c_1, c_2, . . . , c_n$ 表示收买各结点的价格。接下来 $n − 1$ 行，每行两个不超过 $n$ 的正整数，表示树的一条边。保证这些边形成一棵树。最后一行一个正整数 $k$ 表示要回答前 $k$ 个问题。

第一行一个整数，表示第一个问题的答案。如果 $k ≥ 2$ , 第二行按从小到大的顺序输出若干个整数，表示结点编号。如果 $k ≥ 3$ , 第三行输出第三个问题的答案，模 $998244353$

5
500 100 300 200 100
1 2
2 3
2 4
1 5
3

400
2 4 5
1

3
100 100 100
1 2
1 3
3

200
1 2 3
3

所有数据保证 $2 ≤ n ≤ 10^6 , c_i ≤ 10^9 , k ≤ 3$ .