CF1889F.Doremy's Average Tree

Doremy has a rooted tree of size $n$ whose root is vertex $r$. Initially there is a number $w_i$ written on vertex $i$. Doremy can use her power to perform this operation at most $k$ times:

1. Choose a vertex $x$ ($1 \leq x \leq n$).
2. Let $s = \frac{1}{|T|}\sum_{i \in T} w_i$ where $T$ is the set of all vertices in $x$'s subtree.
3. For all $i \in T$, assign $w_i := s$.

Doremy wants to know what is the lexicographically smallest$^\dagger$ array $w$ after performing all the operations. Can you help her?

If there are multiple answers, you may output any one.

$^\dagger$ For arrays $a$ and $b$ both of length $n$, $a$ is lexicographically smaller than $b$ if and only if there exist an index $i$ ($1 \leq i \le n$) such that $a_i \lt b_i$ and for all indices $j$ such that $j \lt i$, $a_j=b_j$ is satisfied.

Doremy 有一棵大小为 $n$ 的有根树，其根节点为顶点 $r$。初始时，顶点 $i$ 上写有一个数字 $w_i$。Doremy 可以使用她的能力至多执行 $k$ 次如下操作：

1. 选择一个顶点 $x$（$1 \leq x \leq n$）；
2. 设 $s = \frac{1}{|T|}\sum_{i \in T} w_i$，其中 $T$ 表示顶点 $x$ 的子树中所有顶点的集合；
3. 对所有 $i \in T$，令 $w_i := s$。

Doremy 想知道：在执行完所有操作后，能得到的字典序最小$^\dagger$的数组 $w$ 是什么？你能帮她吗？

若存在多个满足条件的答案，输出任意一个即可。

$^\dagger$ 对于两个长度均为 $n$ 的数组 $a$ 和 $b$，当且仅当存在某个下标 $i$（$1 \leq i \le n$），使得 $a_i \lt b_i$，且对所有满足 $j \lt i$ 的下标 $j$ 均有 $a_j = b_j$ 时，称 $a$ 的字典序小于 $b$。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains three integers $n$, $r$, $k$ ($2 \le n \le 5000$, $1 \le r \le n$, $0 \le k \le \min(500,n)$).

The second line contains $n$ integers $w_1,w_2,\ldots,w_n$ ($1 \le w_i \le 10^6$).

Each of the next $n-1$ lines contains two integers $u_i$, $v_i$ ($1 \leq u_i, v_i \leq n$), representing an edge between $u_i$ and $v_i$.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ does not exceed $50\,000$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

第一行包含三个整数 $n$、$r$、$k$（$2 \le n \le 5000$，$1 \le r \le n$，$0 \le k \le \min(500,n)$）。

第二行包含 $n$ 个整数 $w_1,w_2,\ldots,w_n$（$1 \le w_i \le 10^6$）。

接下来的 $n-1$ 行中，每行包含两个整数 $u_i$、$v_i$（$1 \leq u_i, v_i \leq n$），表示节点 $u_i$ 与 $v_i$ 之间存在一条边。

保证所给的边构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $50\,000$。

For each test case, In the first line, output a single integer $cnt$ ($0 \le cnt \le k$) — the number of operations you perform.

Then, in the second line output $cnt$ integers $p_1,p_2,\ldots,p_{cnt}$ — $x$ is chosen to be $p_i$ for $i$-th operation.

If there are multiple answers, you may output any one.

对于每个测试用例，在第一行输出一个整数 $cnt$（$0 \le cnt \le k$）—— 表示你执行的操作次数。

然后，在第二行输出 $cnt$ 个整数 $p_1,p_2,\ldots,p_{cnt}$ —— 第 $i$ 次操作中选择的 $x$ 为 $p_i$。

如有多个正确答案，输出任意一个即可。

In the first test case:

At first $w=[1,9,2,6,1,8]$. You can choose some vertex $x$ to perform at most one operation.

• If $x=1$, $w=[\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2}]$.
• If $x=2$, $w=[1,\frac{15}{2},2,\frac{15}{2},1,8]$.
• If $x=3$, $w=[1,9,\frac{11}{3},6,\frac{11}{3},\frac{11}{3}]$.
• If $x \in {4, 5, 6}$, $w=[1,9,2,6,1,8]$.
• If you don't perform any operation, $w=[1,9,2,6,1,8]$.

$w$ is lexicographically smallest when $x=2$.

在第一个测试用例中：

初始时 $w=[1,9,2,6,1,8]$。你可以选择某个顶点 $x$，至多执行一次操作。

• 若 $x=1$，则 $w=[\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2},\frac{9}{2}]$。
• 若 $x=2$，则 $w=[1,\frac{15}{2},2,\frac{15}{2},1,8]$。
• 若 $x=3$，则 $w=[1,9,\frac{11}{3},6,\frac{11}{3},\frac{11}{3}]$。
• 若 $x \in \{4, 5, 6\}$，则 $w=[1,9,2,6,1,8]$。
• 若不执行任何操作，则 $w=[1,9,2,6,1,8]$。

当 $x=2$ 时，$w$ 的字典序最小。