P16445 [XJTUPC 2026] The Whole Rest

> This is our story. You are given a tree with $n$ vertices, numbered $1,2,\dots,n$. Each edge $(u,v)$ has a non-negative integer weight $w(u,v)$. A walk on the tree is defined as a vertex sequence $v_1, v_2, \dots, v_k$ ($k \ge 1$) such that for every $i$ ($1 \le i \le k-1$), there is an edge $(v_i, v_{i+1})$. Note that vertices in the walk may repeat. That is, even if there exist $1 \le i < j \le k$ with $v_i = v_j$, it is still considered a valid walk. The number of edges in the walk is defined as $k-1$, i.e., the number of edges the walk traverses. The set of vertices visited by the walk is defined as $\{v_1, v_2, \dots, v_k\}$, i.e., all vertices that appear in the walk (duplicates are counted only once). The cost of the walk is defined as the bitwise XOR of the weights of the edges along the walk: $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)$, where $\oplus$ denotes bitwise XOR. In particular, when $k=1$ (i.e., the walk contains only one vertex), the cost is $0$. You need to choose a walk that satisfies the following: - It visits all vertices in the tree, i.e., the set of visited vertices equals all $n$ vertices. - Among all walks satisfying condition 1, the cost of the walk is minimum. - If multiple walks satisfy conditions 1 and 2, choose one with the minimum number of edges. - If multiple walks satisfy conditions 1, 2, and 3, any of them will be accepted. Output a walk that satisfies the above conditions, given as a vertex sequence.

The first line contains an integer $n$ ($1 \le n \le 5 \times 10^5$), denoting the number of vertices in the given tree. The next $n-1$ lines each contain three integers $u, v$ and $w$ ($1 \le u,v \le n, 0 \le w < 2^{30}$), indicating that there is an edge $(u,v)$ in the tree with weight $w$. It is guaranteed that the given edges form a tree.

Output two lines. The first line contains an integer $k$ ($1 \le k \le 4 \times 10^6$), denoting the length of the walk's vertex sequence. The second line contains $k$ integers $v_1, v_2, \dots, v_k$, separated by spaces, describing a walk that satisfies the conditions, whose vertex sequence is $v_1, v_2, \dots, v_k$. It can be proven that under the constraints of this problem: - Every vertex label must appear at least once. - For any walk satisfying conditions 1, 2, and 3, the length of its vertex sequence does not exceed $4 \times 10^6$.

Translated by ChatGPT 5