洛谷 P2495 [SDOI2011]消耗战（虚树，dp）

题面

题解

虚树+dp

具体实现

inline void insert(int x) {

	if (top == 1) {s[++top] = x; return ;}

	int lca = query(x, s[top]);

	while (top > 1 && dfn[s[top-1]] >= dfn[lca]) t[s[top-1]].push_back(s[top]), top--;

	if (lca != s[top]) t[lca].push_back(s[top]), s[top] = lca;

	s[++top] = x;

	return ;

}

bool cmp(int a, int b) {

	return dfn[a] < dfn[b];

}//dfn为在dfs序上的位置

main() {//o为输入的关键点

	sort(o+1, o+1+k, cmp);

	s[top = 1] = 1;

	for (int i = 1; i <= k; i++) insert(o[i]);

    for (int i = 1; i < top; i++) t[s[i]].push_back(s[i+1]);

}

然后对于这个虚树\(dp\)

\(a\)数组表示当前点到根这条链路径最小值

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

inline int gi() {

	RG int x = 0; RG char c = getchar(); bool f = 0;

	while (c != '-' && (c < '0' || c > '9')) c = getchar();

	if (c == '-') c = getchar(), f = 1;

	while (c >= '0' && c <= '9') x = x*10+c-'0', c = getchar();

	return f ? -x : x;

}

const int N = 250010, INF = 2147483647;

struct node {

	int to, next, w;

}g[N<<1];

int last[N], gl;

inline void add(int x, int y, int z) {

	g[++gl] = (node) {y, last[x], z};

	last[x] = gl;

	return ;

}

int anc[N][21], dfn[N], cnt, dep[N], a[N];

void init(int u, int fa) {

	anc[u][0] = fa;

	dfn[u] = ++cnt;

	for (int i = 1; i <= 20; i++)

		anc[u][i] = anc[anc[u][i-1]][i-1];

	for (int i = last[u]; i; i = g[i].next) {

		int v = g[i].to;

		if (v == fa) continue;

		dep[v] = dep[u]+1;

		a[v] = min(g[i].w, a[u]);

		init(v, u);

	}

	return ;

}

inline int query(int x, int y) {

	if (dep[x] < dep[y]) swap(x, y);

	for (int i = 20; i >= 0; i--)

		if (dep[anc[x][i]] >= dep[y])

			x = anc[x][i];

	if (x == y) return x;

	for (int i = 20; i >= 0; i--)

		if (anc[x][i] != anc[y][i])

			x = anc[x][i], y = anc[y][i];

	return anc[x][0];

}

vector<int> t[N];

int o[N], s[N], top;

bool cmp(int a, int b) {

	return dfn[a] < dfn[b];

}

inline void insert(int x) {

	if (top == 1) {s[++top] = x; return ;}

	int lca = query(x, s[top]);

	if (lca == s[top]) return ;//祖先都走不到,它肯定也走不到哈

	while (top > 1 && dfn[s[top-1]] >= dfn[lca]) t[s[top-1]].push_back(s[top]), top--;

	if (lca != s[top]) t[lca].push_back(s[top]), s[top] = lca;

	s[++top] = x;

	return ;

}

LL dp(int u) {

	LL S = 0;

	if (!t[u].size()) return a[u];

	for (int i = 0; i < (int)t[u].size(); i++) {

		int v = t[u][i];

		S += dp(v);

	}

	t[u].clear();

	if (u==1) return S;

	return min(S, 1ll*a[u]);

}

int main() {

	//freopen(".in", "r", stdin);

	//freopen(".out", "w", stdout);

	int n = gi();

	for (int i = 1; i < n; i++) {

		int x = gi(), y = gi(), z = gi();

		add(x, y, z); add(y, x, z);

	}

	a[1] = INF;

	init(1, 0);

	int m = gi();

	while (m--) {

		int k = gi();

		for (int i = 1; i <= k; i++)

			o[i] = gi();

		sort(o+1, o+1+k, cmp);

		s[top = 1] = 1;

		for (int i = 1; i <= k; i++) insert(o[i]);

		for (int i = 1; i < top; i++)

			t[s[i]].push_back(s[i+1]);

		printf("%lld\n", dp(1));

	}

	return 0;

}

巴特西

洛谷 P2495 [SDOI2011]消耗战（虚树，dp）

题面

题解

Code

最新文章

热门文章