题目理解

欧艾大陆上有 $n$ 座城市构成一棵树，每座城市出售一种宝石（共 $m$ 种）。K 神有一个宝石收集器，需要按照固定顺序 $P_1, P_2, \ldots, P_c$ 收集宝石。

对于每次询问 $(s, t)$，需要求出从 $s$ 到 $t$ 的最短路径上，按照顺序 $P$ 最多能收集到多少个宝石。

---

关键观察

1. 问题转化

这是一个在树路径上按顺序匹配宝石序列的问题。由于树路径的唯一性，我们可以将问题分解为：

• 从 $s$ 到 LCA 的向上路径
• 从 LCA 到 $t$ 的向下路径

2. 匹配顺序的特殊性

宝石收集必须严格按照 $P_1 \to P_2 \to \cdots \to P_c$ 的顺序进行，不能跳过中间的任何宝石。

---

算法设计

1. 预处理

LCA 预处理

void dfs(int u, int pre) {
    dep[u] = dep[pre] + 1;
    f[u][0] = pre;
    for(int v : g[u])
        if(v != pre) dfs(v, u);
}

宝石链预处理

定义：

• J[u][k]: 从 $u$ 开始，在祖先链上寻找下一个宝石 $P_{i+1}$ 的位置
• K[u][k]: 从 $u$ 开始，在祖先链上寻找前一个宝石 $P_{i-1}$ 的位置
• where[x]: 宝石 $x$ 在序列 $P$ 中的位置

void dfs2(int u, int pre) {
    J[u][0] = lst[nxt[w[u]]];
    K[u][0] = lst[pre[w[u]]];
    int t = lst[w[u]];
    lst[w[u]] = u;
    Start[u] = lst[P[1]];
    
    for(int v : g[u])
        if(v != pre) dfs2(v, u);
    
    lst[w[u]] = t;
}

2. 查询处理

对于每个查询 $(s, t)$：

步骤 1：找到 LCA

int lc = lca(s, t);

步骤 2：在 $s \to LCA$ 路径上找到能匹配的最长前缀

int pos = get(s, lc);  // 找到从s向上能匹配到的最后一个宝石位置

步骤 3：在 $LCA \to t$ 路径上继续匹配剩余宝石

使用二分查找确定最多能匹配多少个宝石：

int l = where[w[pos]] + 1, r = c, ans = where[w[pos]];
while(l <= r) {
    int mid = (l + r) >> 1;
    if(可以在LCA->t路径上匹配到P[mid]) {
        ans = mid;
        l = mid + 1;
    } else {
        r = mid - 1;
    }
}

---

算法正确性

1. 路径分解的正确性

由于树的特性，任意两点间的路径唯一，且必然经过它们的 LCA。将路径分解为 $s \to LCA$ 和 $LCA \to t$ 两部分分别处理是合理的。

2. 匹配顺序的保持

算法严格按照 $P$ 序列的顺序进行匹配：

• 在 $s \to LCA$ 路径上匹配前缀
• 在 $LCA \to t$ 路径上继续匹配后续宝石

3. 二分查找的合理性

宝石匹配具有单调性：如果能匹配前 $k$ 个宝石，那么一定能匹配前 $k-1$ 个宝石。

---

复杂度分析

时间复杂度

• 预处理：
  • LCA 预处理：$O(n \log n)$
  • 宝石链预处理：$O(n \log n)$
• 每次查询：$O(\log n \log c)$
  • LCA 查询：$O(\log n)$
  • 二分查找：$O(\log c)$，每次检查 $O(\log n)$

总复杂度：$O(n \log n + q \log n \log c)$，对于 $n, q \leq 2 \times 10^5$ 可接受。

空间复杂度

• LCA 数组：$O(n \log n)$
• 宝石链数组：$O(n \log n)$
• 其他辅助数组：$O(n + m)$

---

代码实现要点

1. 数组定义

int f[N][20], dep[N];        // LCA相关
int J[N][20], K[N][20];      // 宝石链跳跃
int where[N], nxt[N], pre[N]; // 宝石序列信息
int lst[N], Start[N];        // 临时记录
vector<pair<int, int>> Q[N]; // 离线查询

2. 关键函数

• dfs(): LCA 预处理
• dfs2(): 宝石链预处理
• get(): 在向上路径中匹配宝石前缀
• 二分查找：在向下路径中继续匹配

3. 离线处理

将所有查询按照终点分组，在 DFS 过程中统一处理，避免重复计算。

---

算法标签

• 树结构
• 树上倍增
• 最近公共祖先
• DFS序列
• 倍增数组

---

总结

本题通过巧妙的树链分解和宝石链预处理，将复杂的路径匹配问题转化为可高效求解的形式。算法充分利用了树的特性和宝石序列的顺序性，通过二分查找优化了匹配过程。