求助!树链剖分 MLE
查看原帖
求助!树链剖分 MLE
688783
SilverLi楼主2023/10/1 11:20
#include <iostream>
#include <algorithm>
#include <vector>
#define mid (l + r >> 1)
using namespace std;
constexpr int N = 1e5 + 5;
int n, m;
struct es { int u, v, w, id; } a[N];
int ft[N];
inline void initft() {
	for (int i = 1; i <= n; ++i)	ft[i] = i;
}
int find(int v) { return v == ft[v] ? v : ft[v] = find(ft[v]); }
int vis[N];
vector<int> g[N], W[N];
inline void kls() {
	sort(a + 1, a + m + 1, [](es a, es b) {
		if (a.w == b.w)	return a.u < b.u;
		return a.w < b.w;
	});
	initft();
	for (int i = 1; i <= m; ++i) {
		int u = a[i].u, v = a[i].v, w = a[i].w;
		int fu = find(u), fv = find(v);
		if (fu != fv) {
			ft[fu] = fv;
			vis[a[i].id] = 1;
			g[u].emplace_back(v);
			g[v].emplace_back(u);
			W[u].emplace_back(w);
			W[v].emplace_back(w);
		}
	}
	sort(a + 1, a + m + 1, [](es a, es b) { return a.id < b.id; });
}
int val[N], t[N << 2];
void build(int l, int r, int p) {
	if (l == r) {
		t[p] = val[l];
		return;
	}
	build(l, mid, p << 1);
	build(mid + 1, r, p << 1 | 1);
	t[p] = max(t[p << 1], t[p << 1 | 1]);
}
int max(int l, int r, int S, int T, int p) {
	if (l >= S && r <= T)
		return t[p];
	int ans = 0;
	if (mid >= S)
		ans = max(ans, max(l, mid, S, T, p << 1));
	if (mid < T)
		ans = max(ans, max(mid + 1, r, S, T, p << 1 | 1));
	return ans;
}
int cnt, dfn[N], d[N], f[N];
int top[N], son[N], si[N], v[N];
void dfs(int u, int fa) {
	d[u] = d[fa] + 1;
	f[u] = fa, si[u] = 1;
	for (int l = 0; l < g[u].size(); ++l) {
		int i = g[u][l], w = W[u][l];
		if (i != fa) {
			dfs(i, u);
			v[i] = w;
			si[u] += si[i];
			if (si[i] > si[son[u]])
				son[u] = i;
		}
	}
}
void dfs2(int u, int fa, int deep) {
	dfn[u] = ++cnt, top[u] = deep;
	val[cnt] = v[u];
	if (!son[u])	return;
	dfs2(son[u], u, deep);
	for (int l = 0; l < g[u].size(); ++l) {
		int i = g[u][l];
		if (i != fa && i != son[u])	dfs2(i, u, i);
	}
}
inline int ask(int u, int v) {
	int ans = 0;
	while (top[u] != top[v]) {
		if (d[top[u]] < d[top[v]])	swap(u, v);
		ans = max(ans, max(1, n, dfn[top[u]], dfn[u], 1));
		u = f[top[u]];
	}
	if (d[u] > d[v])	swap(u, v);
	ans = max(ans, max(1, n, dfn[u] + 1, dfn[v], 1));
	return ans;
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		a[i] = {u, v, w, i};
	}
	kls(); dfs(1, 0);
	dfs2(1, 0, 1); build(1, n, 1);
	for (int i = 1; i <= m; ++i)
		if (!vis[i]) {
			int u = a[i].u, v = a[i].v;
			cout << ask(u, v) << '\n';
		}
	return 0;
}

2023/10/1 11:20
加载中...