1function dfs1(u, fa) {
2 size[u] = 1; depth[u] = fa < 0 ? 0 : depth[fa] + 1; par[u] = fa;
3 for (const v of children[u]) {
4 dfs1(v, u); size[u] += size[v];
5 if (heavy[u] < 0 || size[v] > size[heavy[u]]) heavy[u] = v;
6 }
7}
8function dfs2(u, topNode) {
9 top[u] = topNode; dfn[u] = cnt++;
10 if (heavy[u] >= 0) dfs2(heavy[u], topNode); // 先走重儿子，链上 dfn 连续
11 for (const v of children[u])
12 if (v !== heavy[u]) dfs2(v, v); // 轻儿子新开一条链
13}
14function pathQuery(u, v) {
15 let res = 0;
16 while (top[u] !== top[v]) {
17 if (depth[top[u]] < depth[top[v]]) [u, v] = [v, u];
18 res += segQuery(dfn[top[u]], dfn[u]); // 整条重链一段区间
19 u = par[top[u]]; // 跳到链顶的父节点（轻边）
20 }
21 if (depth[u] > depth[v]) [u, v] = [v, u];
22 res += segQuery(dfn[u], dfn[v]); // 同链最后一段
23 return res;
24}