线段树合并做法求卡常
查看原帖
线段树合并做法求卡常
366516
xuyiyang楼主2024/6/25 17:13

做了题,但是 3.24s 加巨大空间太丢人了,能稍稍减小下常数吗,谢谢。时空 O(n+mlog⁡m)\mathcal O(n +m\log m)。参照了 Fuyuki 的做法。

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using ULL = unsigned long long;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)
#define fi first
#define se second

bool Mbe;

//template above

const int N = 2.5e5 + 10, M = N * 2;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

int n, m; vector<int> re[N]; vector<PII> e[N];
int ls[M << 5], rs[M << 5], root[M], idx;
LL s[M << 5];

void insert(int l, int r, int v, int &x) {
	if (!x) x = ++ idx; s[x] = INF;
	if (l == r) return ;
	int mid = l + r >> 1;
	if (v <= mid) insert(l, mid, v, ls[x]);
	if (v > mid) insert(mid + 1, r, v, rs[x]);	
}
void upd(int x) { if (ls[x]) s[ls[x]] = min(s[ls[x]], s[x]); if (rs[x]) s[rs[x]] = min(s[rs[x]], s[x]); s[x] = INF; }
int mer(int l, int r, int x, int y) {
	if (!x || !y) return x | y;
	if (l == r) return s[x] += s[y], x;
	int mid = l + r >> 1; upd(x), upd(y);
	ls[x] = mer(l, mid, ls[x], ls[y]); rs[x] = mer(mid + 1, r, rs[x], rs[y]);
	return x;
}
void dfs(int u, int fa) {
	for (int v : re[u]) insert(1, m, v, root[u]);
	for (PII _ : e[u]) {
		int v = _.fi, w = _.se;
		if (v == fa) continue ;
		dfs(v, u); s[root[v]] = min(s[root[v]], (LL)w); 
		root[u] = mer(1, m, root[u], root[v]);
	}
}
void print(int l, int r, int x) {
	if (l == r) return printf("%lld\n", s[x]), void();
	int mid = l + r >> 1; upd(x);
	print(l, mid, ls[x]), print(mid + 1, r, rs[x]);
}

void mian() {
	scanf("%d", &n);
	for (int i = 0, u, v, w; i < n - 1; i ++ ) {
		scanf("%d%d%d", &u, &v, &w);
		e[u].push_back({v, w}), e[v].push_back({u, w});
	}
	scanf("%d", &m);
	for (int _ = 1; _ <= m; _ ++ ) {
		int k, x; scanf("%d", &k);
		while (k -- ) { scanf("%d", &x); re[x].push_back(_); }
	}
	dfs(1, -1); print(1, m, root[1]);
}

bool Med;
int main() {
	fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
	#ifdef xuyiyang
		freopen(".in", "r", stdin); freopen(".out", "w", stdout);
	#endif

	int T = 1; 
	while (T -- ) mian();

	fprintf(stderr, "%.3lf ms\n", 1e3 * clock() / CLOCKS_PER_SEC);
	return 0;
}
2024/6/25 17:13
加载中...