树上的 mex
Time Limit : 15000/7500ms (Java/Other) Memory Limit : 524288/524288K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
给定一棵 $ n $ 个点的树，树上第 $ i $ 个点带非负整数点权 $ a_i $。
定义树上一条简单路径的价值是简单路径上所有点的点权构成集合的 $ \operatorname{mex} $，即最小的没有在集合中出现过的非负整数。
求树上所有简单路径的价值的最大值，以及价值为这个最大值的简单路径数量，其中我们认为 $ x $ 到 $ y $ 和 $ y $ 到 $ x $ 是两条路径。
由于一些特殊的原因，树上的点权分布比较特殊。具体而言，对于任意某个特定点权 $ v $，所有的点权为 $ v $ 的点构成的点集合：
$$
S(v)=\set{x|a_x=v}
$$
都存在树上的一条简单路径，使得 $ S(v) $ 中的所有点都在这条简单路径上。
定义树上一条简单路径的价值是简单路径上所有点的点权构成集合的 $ \operatorname{mex} $，即最小的没有在集合中出现过的非负整数。
求树上所有简单路径的价值的最大值，以及价值为这个最大值的简单路径数量，其中我们认为 $ x $ 到 $ y $ 和 $ y $ 到 $ x $ 是两条路径。
由于一些特殊的原因，树上的点权分布比较特殊。具体而言，对于任意某个特定点权 $ v $，所有的点权为 $ v $ 的点构成的点集合：
$$
S(v)=\set{x|a_x=v}
$$
都存在树上的一条简单路径，使得 $ S(v) $ 中的所有点都在这条简单路径上。
Input
本题单个测试点内包含多组测试数据。
第一行一个整数 $ T(1\leq T\leq 10) $，表示数据组数。
对于每组数据，第一行一个整数 $ n $ $ (3\leq n\leq 7\times 10^4) $，表示树的点数。
第二行 $n$ 个整数 $ a_1,a_2,\cdots,a_n $ $ (0\leq a_i\leq n) $，表示树上每个点的点权。
接下来 $ n-1 $ 行，每行两个整数 $ x,y $ $ (1\leq x,y\leq n) $，表示树上有一条连接点 $x,y$ 的边，保证构成一棵树。
测试点保证所有数据中 $ n $ 的总和不超过 $ 3.6\times 10^5 $。
第一行一个整数 $ T(1\leq T\leq 10) $，表示数据组数。
对于每组数据，第一行一个整数 $ n $ $ (3\leq n\leq 7\times 10^4) $，表示树的点数。
第二行 $n$ 个整数 $ a_1,a_2,\cdots,a_n $ $ (0\leq a_i\leq n) $，表示树上每个点的点权。
接下来 $ n-1 $ 行，每行两个整数 $ x,y $ $ (1\leq x,y\leq n) $，表示树上有一条连接点 $x,y$ 的边，保证构成一棵树。
测试点保证所有数据中 $ n $ 的总和不超过 $ 3.6\times 10^5 $。
Output
对于每组数据输出一行两个整数，分别表示价值的最大值和对应的简单路径数量。
Sample Input
3 5 0 1 2 3 4 1 2 2 3 3 4 4 5 6 0 1 1 0 4 2 1 3 2 3 2 4 4 5 4 6 6 0 1 1 0 4 2 1 3 2 3 3 4 4 5 4 6
Sample Output
5 2 3 6 3 6
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）