代码 TLE 了两个点,向各位大佬求助
查看原帖
代码 TLE 了两个点,向各位大佬求助
674967
xz001楼主2023/8/16 10:21

我写了一份树链剖分求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,求助大佬

2023/8/16 10:21
加载中...