问题分析

题目给出一棵 $n$ 个节点的树，每个节点有一个宝石类型 $w_i$。宝石收集器有一个固定的收集顺序 $P_1, P_2, \dots, P_c$，必须按顺序收集宝石。每次询问从 $s$ 到 $t$ 的简单路径上，按顺序最多能收集到多少颗宝石。

核心思路

1. 路径分解与 LCA
   任意两点 $s$ 和 $t$ 之间的路径可以拆分为 $s \to \mathrm{LCA}(s,t)$ 和 $\mathrm{LCA}(s,t) \to t$ 两段。由于收集顺序是固定的，需要分别处理这两段路径上的宝石收集情况。

2. 倍增预处理

   • 使用倍增法预处理每个节点的祖先关系，用于快速求 LCA。
   • 预处理两个关键信息：
     • 正向链：从当前节点向上，下一个应该收集的宝石类型出现在哪个祖先节点。
     • 反向链：从当前节点向上，上一个已经收集的宝石类型出现在哪个祖先节点。

3. 二分答案
   对于每个查询，先确定从起点 $s$ 到 LCA 能收集到的宝石数量 $k$，然后二分判断能否在 $t$ 到 LCA 的路径上继续收集到更多宝石，从而得到最大收集数量。

算法流程

1. 读入与初始化

   • 读入树结构、宝石顺序、节点宝石类型。
   • 建立宝石顺序的映射关系，便于快速判断下一个/上一个宝石类型。

2. 第一次 DFS

   • 计算深度和父节点信息，用于 LCA 查询。

3. 第二次 DFS

   • 维护每种宝石最后一次出现的节点（利用 DFS 栈特性）。
   • 计算正向链和反向链的倍增数组。

4. 第三次 DFS（处理查询）

   • 对每个查询 $(s, t)$：
     • 计算 LCA。
     • 确定从 $s$ 到 LCA 能收集到的宝石数量。
     • 二分判断从 LCA 到 $t$ 能否收集更多宝石。
   • 输出答案。

复杂度分析

• 预处理：$O(n \log n)$
• 每次查询：$O(\log n \cdot \log c)$（LCA + 二分答案）
• 总复杂度：$O((n + q) \log n)$，可以处理 $n, q \le 2 \times 10^5$ 的数据规模。

总结

该题结合了树上路径查询与顺序匹配问题，通过倍增法和二分答案高效解决了在树上按固定顺序收集物品的最大数量查询，是一道较为复杂的树上数据结构题目。