我写了一份树链剖分求lca,但T了两个点
#include<bits/stdc++.h>
using namespace std;
const int N = 500005;
vector<int> a[N];
int n, m, root, siz[N], bl[N], ms[N], fa[N], dpt[N];
inline int get_size (int u, int f) {
siz[u] = 1, fa[u] = f;
dpt[u] = dpt[f] + 1;
for (register auto v: a[u]) {
if (v != f) {
siz[u] += get_size (v, u);
}
}
return siz[u];
}
inline void get_belong (int u, int f) {
for (register auto v: a[u]) {
if (v != f) {
if (siz[v] > ms[u]) ms[u] = v;
}
}
for (register auto v: a[u]) {
if (v != f) {
if (v != ms[u]) {
bl[v] = v;
get_belong (v, u);
} else {
bl[v] = bl[u];
get_belong (v, u);
}
}
}
return;
}
inline int lca (register int u, register int v) {
while (bl[u] != bl[v]) {
if (min(dpt[fa[u]], dpt[bl[u]]) < min(dpt[fa[v]], dpt[bl[v]])) swap(u, v);
if (u == bl[u]) u = fa[u];
else u = bl[u];
}
if (dpt[u] < dpt[v]) return u;
else return v;
}
int main() {
scanf("%d%d%d",&n, &m, &root);
bl[root] = root;
for (register int i = 1; i < n; ++ i) {
register int u, v;
scanf("%d%d",&u, &v);
a[u].push_back(v);
a[v].push_back(u);
}
get_size (root, 0);
get_belong (root, 0);
while (m -- ) {
register int u, v;
scanf("%d%d",&u, &v);
printf("%d\n",(u != v) ? lca(u, v) : u);
}
return 0;
}
不管怎么改都T,求助大佬