前置：莫队，LCA（太简单了懒得写(bushi)）
1. 树 -> 链
用欧拉序将树转化成序列，然后我们可以发现：
-
若 \text{lca}(u,v) = u，u \to v 的路径为 in_u 到 in_v 的区间中所有只出现一次的点构成的路径。
-
若 \text{lca}(u, v) \ne u，u \to v 的路径为 out_u 到 in_v 的区间中所有只出现一次的点和他们的 \text{lca}构成的路径。
于是乎，链上信息就转化为了区间信息。好的，莫队启动！
2. 例题
Gym-100962F Frank Sinatra
链上 \text{mex}。
我们知道区间 \text{mex} 可以用莫队 + 分块做。
然后套树上莫队板子即可。
注意此题为边权，不用考虑 \text{lca}，将边权存到深度较深的节点中即可。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, b;
map<int, int> mp;
int tmp, to[N], a[N];
struct edge {
int to, col, nxt;
}e[N * 2];
int h[N], tot;
void add (int u, int v, int w) {
e[++ tot] = {v, w, h[u]}, h[u] = tot;
}
int dfn[N], idx, in[N], out[N], ans[N];
int c[N];
void dfs (int u, int fath) {
in[u] = ++ idx, dfn[idx] = u;
for (int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to, col = e[i].col;
if(v == fath) continue;
c[v] = col + 1;
dfs(v, u);
}
out[u] = ++ idx, dfn[idx] = u;
}
struct ask {
int l, r, id;
}q[N];
bool cmp (ask x, ask y) {
if((x.l - 1) / b + 1 != (y.l - 1) / b + 1) return x.l < y.l;
return x.r < y.r;
}
namespace block {
int len, siz, num;
int bel[N], le[N], ri[N], cnt[N], hav[N];
void init () {
siz = 400;
for (int i = 1; i <= len; i ++) {
bel[i] = (i - 1) / siz + 1, hav[bel[i]] ++;
if(bel[i] != bel[i - 1]) le[bel[i]] = i, ri[bel[i] - 1] = i - 1;
}
num = bel[n], ri[bel[n]] = n;
}
void add (int x) {
if(x > len) return;
cnt[x] ++;
if(cnt[x] == 0) hav[bel[x]] --;
}
void del (int x) {
if(x > len) return;
cnt[x] --;
if(cnt[x] == 1) hav[bel[x]] ++;
}
int getmex () {
for (int i = 1; i <= num; i ++){
if(hav[i])
for (int p = le[i]; p <= ri[i]; p ++)
if(!cnt[p]) return p - 1;
}
return len;
}
};
bool vis[N];
void Add (int pos) {
int u = dfn[pos];
if(!vis[u]) block::add(c[u]);
else block::del(c[u]);
vis[u] ^= 1;
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
b = sqrt(n * 2);
block::len = n + 1, block::init();
for (int i = 1; i < n; i ++) {
int u, v, col;
cin >> u >> v >> col;
add(u, v, col), add(v, u, col);
}
dfs(1, 0);
for (int i = 1; i <= m; i ++) {
int u, v;
cin >> u >> v;
if(in[u] > in[v]) swap(u, v);
q[i].l = out[u], q[i].r = in[v], q[i].id = i;
}
sort(q + 1, q + 1 + m, cmp);
int l = q[1].l, r = q[1].l - 1;
for (int i = 1; i <= m; i ++) {
while(l < q[i].l) Add(l ++);
while(l > q[i].l) Add(-- l);
while(r < q[i].r) Add(++ r);
while(r > q[i].r) Add(r --);
ans[q[i].id] = block::getmex();
}
for (int i = 1; i <= m; i ++) cout << ans[i] << endl;
return 0;
}