CF369C Valera and Elections

Valera 所居住的城市即将举行市议会选举。 这座城市有 $n$ 个区和 $n-1$ 条双向道路。已知从任一区出发都存在一条道路路径可以到达其它任一区。我们将所有区按照某种方式编号为 $1$ 到 $n$。此外，对于每一条道路，居民们已经决定它是否为“问题道路”。“问题道路”是指需要修缮的道路。 现有 $n$ 名候选人参与选举。我们将所有候选人按照某种方式编号为 $1$ 到 $n$。如果编号为 $i$ 的候选人当选市议会，他将履行一项承诺——修缮从第 $i$ 区到位于第 $1$ 区（市议会所在地）的所有“问题道路”。 请帮助 Valera 确定一个候选人子集，使得如果该子集中的所有候选人当选后，全市所有“问题道路”都会得到修缮。如果存在多个这样的子集，要求选择最小规模（人数最少）的子集。

第一行包含一个正整数 $n$（$2 \leq n \leq 10^{5}$），表示城市的区数。 接下来 $n-1$ 行，每行包含三个正整数 $x_i, y_i, t_i$（$1 \leq x_i, y_i \leq n$，$1 \leq t_i \leq 2$），表示连接第 $x_i$ 区和第 $y_i$ 区的第 $i$ 条双向道路，以及该道路的类型。如果 $t_i=1$，则第 $i$ 条道路不是“问题道路”；如果 $t_i=2$，则第 $i$ 条道路是“问题道路”。 保证城市的图结构是一棵树。

第一行输出一个非负整数 $k$，表示所需候选人子集的最小规模。第二行输出 $k$ 个用空格分隔的正整数 $a_1, a_2, \dots, a_k$，表示该子集中候选人的编号。如果有多种方案，可以输出任意一个。

由 ChatGPT 5 翻译