抽象代码求调
查看原帖
抽象代码求调
852144
Loser_Syx楼主2023/12/29 22:15

看上去是错了 st 表的 min 查询部分。

#include <ctime>
#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
#define int long long
#define debug puts("qwq")
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
#define all(x) x.begin(), x.end()
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Args> inline void read(T &x, Args &...args) {
		read(x), read(args...);
	}
	template <typename T>
	inline void write(T x, char ch) {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
	void quit() {
		exit(0);
	}
} using namespace FastIO;
const int N = 1e5 + 19;
const int MAX_LOG = 20;
int dep[N], cnt, a[N], dfn[N], top[N], fa[N], siz[N], val[N], son[N], now[N];
vector<pair<int, int> > g[N];
int st[MAX_LOG][N], ts[MAX_LOG][N];
void initst(int n) {
	for (int i = 1; i <= n; ++i) {
		st[0][i] = ts[0][i] = a[i];
	}
	int t = __lg(n);
	for (int j = 1; j <= t; j ++) {
		for (int i = 1; i <= n - (1 << j) + 1; i ++) {
			ts[j][i] = min(ts[j - 1][i], ts[j - 1][i + (1 << (j - 1))]);
			st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		}
	}
}
int search_max(int l, int r) {
	int k = __lg(r - l + 1);
	return max(st[k][l], st[k][r - (1 << k) + 1]);
}
int search_min(int l, int r) {
	int k = __lg(r - l + 1);
	return min(ts[k][l], ts[k][r - (1 << k) + 1]);
}
void dfs1(int u, int f) {
	fa[u] = f;
	siz[u] = 1;
	for (pair<int, int> i : g[u]) {
		if (i.first != f) {
			val[i.first] = i.second;
			dfs1(i.first, u);
			if (siz[i.first] > siz[son[u]]) son[u] = i.first;
			siz[u] += siz[i.first];
		}
	}
}
void dfs2(int u, int f) {
	dfn[u] = ++cnt;
	now[cnt] = u;
	dep[u] = dep[fa[u]] + 1;
	top[u] = f;
	if (son[u]) dfs2(son[u], f);
	for (pair<int, int> i : g[u]) {
		if (i.first != fa[u] && i.first != son[u]) {
			dfs2(i.first, i.first);
		}
	}
}
void lca(int u, int v) {
	int ans1 = -1e9, ans2 = 1e9;
	while (top[u] != top[v]) {
		if (dep[top[u]] > dep[top[v]]) swap(u, v);
		ans1 = max(ans1, search_max(dfn[top[v]], dfn[v]));
		ans2 = min(ans2, search_min(dfn[top[v]], dfn[v]));
		v = fa[top[v]];
	}
	if (dep[top[u]] > dep[top[v]]) swap(u, v);
	ans1 = max(ans1, search_max(dfn[u], dfn[v]));
	ans2 = min(ans2, search_min(dfn[u], dfn[v]));
	write(ans2, ' ');
	write(ans1, '\n');
}
signed main() {
	int n;
	read(n);
	for (int i = 1; i < n; ++i) {
		int u, v, w;
		read(u, v, w);
		g[u].emplace_back(make_pair(v, w));
		g[v].emplace_back(make_pair(u, w));
	}
	dfs1(1, 1);
	dfs2(1, 1);
	for (int i = 1; i <= n; ++i) a[i] = val[now[i]];
	initst(n);
	int q;
	read(q);
	while (q--) {
		int x, y;
		read(x, y);
		lca(x, y);
	}
	return 0;
}
2023/12/29 22:15
加载中...