#P17137. Grand Mex

    ID: 17276 传统题 4000ms 512MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>图论2-SAT数据结构强连通分量CF19002026杭电暑期多校第6场Contest1234

Grand Mex

1001. Grand Mex

题目描述

完整题目参见:PDF 题面

有 nn 个整数 a1,a2,…,ana_1,a_2, \ldots ,a_ n,初始时它们全部等于 00。

接下来依次进行 n−1n-1 次操作。第 ii 次操作给出两个不同的下标 xi,yix_i,y_i。你需要选择其中一个下标。

如果选择 xix_i,则执行

$$a_{x_i}\leftarrow a_{x_i}+1,\qquad a_{y_i}\leftarrow 0.$$

如果选择 yiy_i,则执行

$$a_{y_i}\leftarrow a_{y_i}+1,\qquad a_{x_i}\leftarrow 0.$$

保证将所有 (xi,yi)\lparen x_i,y_i \rparen 看作无向边后,它们构成一棵包含 nn 个点的树。

你必须按照输入顺序完成全部操作。请最小化最终序列 aa 的 mex⁡\operatorname{mex},并构造一种达到最小值的操作方案。

序列的 mex⁡\operatorname{mex} 定义为没有在序列中出现的最小非负整数。例如,mex⁡([0,2,2])=1\operatorname{mex}([0,2,2])=1。

输入格式

第一行包含一个整数 TT(1≤T≤2×1051\le T\le 2\times 10^5),表示测试数据的组数。

对于每组测试数据:

  • 第一行包含一个整数 nn(2≤n≤5×1052\le n\le 5\times 10^5)。

  • 接下来 n−1n-1 行,第 ii 行包含两个整数 xi,yix_i,y_i(1≤xi,yi≤n1\le x_i,y_i\le n,xi≠yix_i\ne y_i),表示第 ii 次操作涉及的两个下标。

保证每组测试数据中的所有边构成一棵树,且对于所有测试数据 ∑n≤106\sum n \le 10^6。

输出格式

对于每组测试数据:

第一行输出一个整数,表示最终序列的最小可能 mex⁡\operatorname{mex}。

第二行输出 n−1n-1 个整数 s1,s2,…,sn−1s_1,s_2,\ldots,s_{n-1}。其中 sis_i 必须等于 xix_i 或 yiy_i,表示在第 ii 次操作中选择 asia_{s_i} 加一,并将另一个数清零。

如果存在多种最优方案,输出任意一种。

样例输入

3
2
1 2
6
4 3
2 1
3 1
5 3
6 1
8
4 7
2 5
1 3
6 2
3 6
8 3
2 4

样例输出

2
2
2
4 2 3 5 6
1
4 2 3 2 3 3 2

提示

样例输出分别给出了一种最优操作方案。可能存在其他正确的最优方案。

来源:2026杭电多校-测试专用(山西实验) 原题链接:http://acm.hdu.edu.cn/contest/problem_show.php?cid=1234&pid=1001 ⚠ 本题为 Special Judge。官方数据中的 .out 多为评测机判定输出(如 AC/OK/Correct/yes),导入后需自行提供 checker 方可正确评测。