#P17958. Maximum Mex
Maximum Mex
Maximum Mex
题目描述
给定一棵有 个结点的树。每条边 上写有一个非负整数 ,且每个数值至多出现在六条边上。
对于任意两个结点 ,考虑它们之间唯一简单路径上的全部边权。定义这条路径的价值为这些边权的 mex,即没有在路径上出现的最小非负整数。
求所有结点对对应的路径价值的最大值。
输入格式
第一行一个整数 ,表示测试用例数,。
每组测试用例的第一行包含一个整数 ,。
接下来 行,每行三个整数 ,表示一条边及其边权,满足 、、。
保证给出的边构成一棵树,且每一种边权在该测试用例中出现的次数不超过六次。
所有测试用例的 之和不超过 。
输出格式
每组测试用例输出一行一个整数,表示路径价值的最大值。
样例 1
输入
3
4
2 1 0
1 3 1
1 4 2
5
1 2 0
1 3 1
2 4 0
2 5 2
10
2 3 0
6 10 1
3 7 2
10 9 0
8 2 0
1 9 2
5 2 1
9 3 2
4 10 3
输出
2
3
4