分数: 600 点
问题陈述
有 N 有不同姓氏的人,以及姓氏 i- 第一个人有参数 (X_i, Y_i, Z_i)。不同的姓氏可能具有相同的参数。 发生以下事件 N - 1 次。
- 两个人成为父母,一个孩子出现。父母二人相继去世。孩子选择父母两个姓氏中较大的一个作为自己的姓氏。带参数的姓氏 (x_1, y_1, z_1) 比带参数的姓氏强 (x_2, y_2, z_2) if x_1 > x_2, y_1 > y_2,和 z_1 > z_2 全部保留。如果父母双方的姓氏都不比对方的姓氏强,那么孩子会随机选择父母两个姓氏中的一个。
找出其中的人数 N 姓氏可以是最后剩下的人的姓氏的人。
你被给予 T 测试用例;逐一解决。
约束
- 1 \le T \le 2 \times 10^5
- 2 \le N \le 2 \times 10^5
- 1 \le X_i, Y_i, Z_i \le N
- 总和 N 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_N Y_N Z_N
输出
输出 T 行。
的 树的 i- 第行应包含姓氏可以是最后剩余人员姓氏的人数 i- 第一个测试用例。
示例输入 1
3 4 3 4 4 2 2 2 4 3 3 1 1 1 3 2 1 1 1 2 1 1 1 2 3 2 2 2 2 2 2 1 1 1
示例输出 1
2 3 2
对于第一个测试用例,以下是可能的事件序列。
让姓氏 i 表示姓氏 i第一个人。
- 有姓氏的人 2 和 4 成为父母。姓氏 2 更强,所以孩子有姓氏 2.
- 有姓氏的人 2 和 3 成为父母。姓氏 3 更强,所以孩子有姓氏 3.
- 有姓氏的人 1 和 3 成为父母。都不姓 1 也不是姓氏 3 比另一个姓氏强,所以孩子选择其中一个姓氏 1 or 3.
都不姓 2 也不是姓氏 4 可以是最后剩下的人的姓氏,所以答案是 2.