算是个笔记吧。

众所周知，用 Tarjan 求 LCA 可以在 $\Theta(n+m)$ 的时间内完成。

UPD1：有误，最慢可以到一个 $\log$。

UPD2：找到个论文，至少期望还是线性复杂度。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 9;
int n, m, s;
int fa[N];
int ans[N];
vector<pair<int, int>> q[N];
vector<int> es[N];
int findf(int x) { return fa[x] == x ? x : fa[x] = findf(fa[x]); }
void dfs(int x, int f) {
  for (int y : es[x])
    if (y != f) dfs(y, x);
  for (auto [y, id] : q[x])
    if (!ans[id])
      ans[id] = -1;
    else if (ans[id] == -1)
      ans[id] = findf(y);
  fa[x] = f;
}
int main() {
  cin >> n >> m >> s;
  for (int u, v, i = 1; i < n; ++i)
    cin >> u >> v, es[u].push_back(v), es[v].push_back(u);
  for (int u, v, i = 1; i <= m; ++i)
    cin >> u >> v, q[u].emplace_back(v, i), q[v].emplace_back(u, i);
  for (int i = 1; i <= n; ++i) fa[i] = i;
  dfs(s, 0);
  for (int i = 1; i <= m; ++i) cout << ans[i] << endl;
  return 0;
}

（代码比较丑，意会即可。）

这个算法的精髓之一就在于其中一个点在并查集上跳到根，就是 LCA。如果我们在 dfs 之后把邻接表倒过来再来一次，那么另一个点跳到根也能跳到 LCA。

而树上链查询是可以分成两段分别到 LCA 的查询（这个 LCA 甚至不用显式求出），而一段到 LCA 的查询显然可以把 Tarjan 算法里的并查集加装成带权版轻松搞定。

似乎挺漂亮的一个玩意。代码写过但没找到纯板题，写的那题（链查询最大值）无关代码过多，所以不贴了。

以上。