求助,虚树用树剖+ST表维护最小值MLE(50分),我不理解
查看原帖
求助,虚树用树剖+ST表维护最小值MLE(50分),我不理解
330239
Tapower楼主2022/9/17 21:27

代码开的数组虽然有亿点多,下面是丑陋的代码。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define Mp make_pair
#define eb emplace_back
#define fir(x, y, z) for(int x = (y); x <= (z); ++ x)
#define fdr(x, y, z) for(int x = (y); x >= (z); -- x)
#define fre(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

namespace io {
	const int n = 1e6;
	char c, b[n], *i, *j;
	inline char gc() {
		if (i == j) {
			j = (i = b) + fread(b, 1, n, stdin);
			if (i == j) return EOF;
		} return *i ++;
	}
	#define gc getchar
	template <typename T = int>
	inline T read() {
		T s = 0; int x = 0;
		while (!isdigit(c = gc())) x |= c == '-';
		for (; isdigit(c); c = gc())
			s = (s << 1) + (s << 3) + (c & 15);
		return x ? - s : s;
	};
}

using io :: read;

const int N = 500005;
const int inf = 1e9;

typedef int ary[N];

int n, m, tot, cnt, ver[N << 1], nxt[N << 1], val[N << 1], Top, mn[N][19];
ary head, dfn, siz, f, top, dep, son, sta, a, bot, vis, Log, w;

inline void Add_edge(int x, int y, int w) {
	ver[++ tot] = y; nxt[tot] = head[x];
	val[tot] = w; head[x] = tot;
	ver[++ tot] = x; nxt[tot] = head[y];
	val[tot] = w; head[y] = tot;
}

inline void Dfs1(int x, int fa) {
	siz[x] = 1, f[x] = fa;
	dep[x] = dep[fa] + 1;
	for (int i = head[x], y; i; i = nxt[i])
		if ((y = ver[i]) != fa) {
			Dfs1(y, x); siz[x] += siz[y];
			if (siz[y] > siz[son[x]]) son[x] = y;
		}
}

inline void Dfs2(int x, int fa, int v) {
	mn[dfn[x] = ++ cnt][0] = v;
	top[x] = x == son[fa] ? top[fa] : x;
	bot[x] = x;
	if (son[x]) {
		int Val;
		for (int i = head[x]; i; i = nxt[i])
			if (ver[i] == son[x]) {
				Val = val[i]; break;
			}
		Dfs2(son[x], x, Val);
		bot[x] = bot[son[x]];
	}
	for (int i = head[x], y; i; i = nxt[i])
		if ((y = ver[i]) != fa && son[x] != y)
			Dfs2(y, x, val[i]);
}

inline void Init(int l, int r) {
	if (l > r) swap(l, r);
	int len = r - l + 1, LOG = 0;
	while (1 << LOG + 1 <= len) ++ LOG;
	fir (j, 1, LOG) fir (i, l, r - (1 << j) + 1)
		mn[i][j] = min(mn[i][j - 1], mn[i + (1 << j - 1)][j - 1]);
}

inline int ask(int l, int r) {
	if (l > r) swap(l, r);
	int log = Log[r - l + 1];
	return min(mn[l][log], mn[r - (1 << log) + 1][log]);
}

inline int Lca(int x, int y, int &Min) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		Min = min(Min, ask(dfn[top[x]], dfn[x]));
		x = f[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	Min = min(Min, ask(dfn[x], dfn[y]));
	return x;
}

inline bool cmp(int x, int y) {
	return dfn[x] < dfn[y];
}

inline ll Dp(int x, int fa) {
	ll sum = 0;
	for (int i = head[x], y; i; i = nxt[i])
		if ((y = ver[i]) != fa) {
			if (vis[y]) sum += val[i];
			else sum += min(Dp(y, x), 1ll * val[i]);
		}
	return sum == 0 ? 1e18 : sum;
}

signed main() {
	n = read();
	fir (i, 2, n) {
		int x = read(), y = read(), w = read();
		Add_edge(x, y, w);
	}
	memset(mn, 0x3f, sizeof mn);
	Dfs1(1, 0); Dfs2(1, 0, inf);
	fir (i, 1, n) if (!vis[top[i]])
		Init(dfn[top[i]], dfn[bot[i]]);
	fir (i, 2, n) Log[i] = Log[i >> 1] + 1;
	fir (i, 1, n) head[i] = vis[i] = 0;
	for (int q = read(); q --;) {
		sta[Top = 1] = 1;
		head[1] = 0;
		m = read();
		fir (i, 1, m) a[i] = read();
		sort(a + 1, a + m + 1);
		m = unique(a + 1, a + m + 1) - a - 1;
		sort(a + 1, a + m + 1, cmp);
		fir (i, 1, m) vis[a[i]] = 1;
		tot = 0;
		fir (i, a[1] == 1 ? 2 : 1, m) {
			int x, lca = Lca(sta[Top], a[i], x);
			if (lca != sta[Top]) {
				while (dfn[lca] < dfn[sta[Top - 1]])
					Add_edge(sta[Top], sta[-- Top], w[Top + 1]);
				if (lca != sta[Top - 1]) {
					head[lca] = 0;
					w[Top] = inf;
					Lca(sta[Top], lca, w[Top]);
					Add_edge(lca, sta[Top], w[Top]);
					sta[Top] = lca;
					w[Top] = inf;
					Lca(lca, sta[Top - 1], w[Top]);
				} else {
					Add_edge(lca, sta[Top], w[Top]);
					-- Top;
				}
			}
			head[a[i]] = 0;
			sta[++ Top] = a[i];
			w[Top] = inf;
			Lca(a[i], sta[Top - 1], w[Top]);
		}
		fir (i, 2, Top) Add_edge(sta[i - 1], sta[i], w[i]);
		printf("%lld\n", Dp(1, 0));
		fir (i, 1, m) vis[a[i]] = 0;
	}
	return 0;
}
2022/9/17 21:27
加载中...