题解

思路

把从根到每个节点的值频率向量保存成一个可持久化版本。任意路径的频率向量都能由四个根路径版本相加减得到。若能快速判断某个值域内两条路径的频率向量是否相同，就可以在值域线段树上递归，只进入确有差异的儿子，并在找到 $k$ 个值后停止。

做法

先迭代遍历树，建立倍增祖先表并求出每个节点的父亲、深度和根路径版本。节点 $v$ 的版本在父亲版本上把 $a_v$ 加一。

对路径 $(u,v)$，令 $w=\operatorname{lca}(u,v)$，则它的频率向量为

在线段树的每个区间中保存频率向量的双 64 位固定种子随机线性哈希。比较两条路径在当前区间的四版本组合哈希：相同则跳过；不同则递归左右儿子。到达叶子时，该叶子对应的值就是一个频率不同的答案。按值从小到大搜索并在收集到 $k$ 个值后停止。

随机权值和种子固定，构建可以完全复现。双 64 位哈希把碰撞概率降到可忽略量级；正式数据还由独立实现、精确小规模暴力和输出 checker 共同核验。

子任务算法

• 子任务 1：每次分别还原两条路径，用映射表直接统计所有值的出现次数，复杂度 $O(nq)$。
• 子任务 2：预处理每个值在每个根路径上的精确出现次数，再枚举至多 $1000$ 个值，复杂度 $O(n\max a+q\max a)$。
• 子任务 3：使用可持久化值域线段树、LCA 与双哈希下降，每次只访问通向答案的区间。

正确性说明

根路径版本的四项容斥恰好保留 $u$ 到 $v$ 路径上的每个节点，因此得到的频率向量正确。若某个区间内两条路径的频率向量不同，则至少一个叶子值的频率不同；递归最终会到达这样的叶子。反之，被跳过的区间哈希一致，在没有碰撞时其中所有频率都相同。于是输出的每个值都合法，并且若差异值不足 $k$ 个会全部找到，否则恰好找到 $k$ 个。

复杂度

预处理时间和空间均为 $O(n\log A)$，其中 $A=10^5$。每次询问访问至多 $O(k\log A)$ 个相关节点，时间为 $O(k\log A)$。