P16445 [XJTUPC 2026] The Whole Rest

> 这，就是我们的故事。 给定一棵包含 $n$ 个顶点的树，顶点编号为 $1,2,\dots,n$。每条边 $(u,v)$ 有一个非负整数权值 $w(u,v)$。 定义树上的一条途径为一个顶点序列 $v_1, v_2, \dots, v_k$（$k \ge 1$），满足对于任意的 $i$（$1\le i\le k-1$），都有一条边 $(v_i,v_{i+1})$。请注意，途径中的顶点可以重复，即如果存在 $1\le i< j\le k$ 满足 $v_i=v_j$，仍然认为这是一条途径。 途径的边数定义为 $k-1$，即途径经过的边的数量。 途径经过的顶点集定义为 $\{v_1, v_2, \dots, v_k\}$，即途径中所有出现过的顶点（重复只计一次）。 途径的代价定义为沿途经过的边的权值的异或和：$w(v_1, v_2)\oplus w(v_2, v_3)\oplus w(v_3, v_4)\oplus\cdots\oplus w(v_{k-1},v_k)$，其中 $\oplus$ 表示按位异或。特别地，当 $k=1$ 时（即途径只包含一个顶点），途径的代价为 $0$。 要求选择一条途径，满足如下条件： - 它经过树中所有的顶点，即途径经过的顶点集等于全部 $n$ 个顶点； - 在所有满足条件 1 的途径中，途径的代价最小； - 如果有多条途径同时满足条件 1 和 2，则选择途径的边数最少的； - 如果有多条途径同时满足条件 1、2 和 3，则选择任意一条，都会被视为正确。 输出一条满足上述条件的途径，以顶点序列的形式给出。

输入的第一行，包含一个整数 $n$（$1 \le n \le 5 \times 10^5$），表示给定的树有 $n$ 个顶点。 接下来 $n-1$ 行，每行包含三个整数 $u,v$ 和 $w$（$1\le u,v\le n, 0\le w

输出两行。第一行包含一个整数 $k$（$1 \le k \le 4 \times 10^6$），表示途径的顶点序列的长度。 第二行包含 $k$ 个整数 $v_1, v_2, \dots, v_k$，用一个空格分隔，表示一条满足条件的途径，其顶点序列为 $v_1, v_2, \dots, v_k$。 可以证明，在题目的约束下： - 所有顶点的编号都需要至少出现一次； - 对于任意一条满足题目条件 1、2 和 3 的途径，其顶点序列的长度均不超过 $4 \times 10^6$。