← 返回题目列表

AtCoder · arc215_c

C. 强姓

中文机器翻译题面 查看原题

分数: 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.