山东省实验中学 2023 秋提高级友好学校赛前联测 3

AisDaeun 11 2023-10-29

生成树 (tree)

考虑最小生成树的情况,我们可以证明要求的最小生成树就是原图本身:若存在一条不在原图上的边(x, y)被选进最小生成树,设原图中从x到y的路径经过k,由于所有边权大于等于1,则(x, y)的边权一定大于(x, k)(k, y),所以(x, y)一定不会被选进最小生成树。

考虑最大生成树的情况,对于任意点u,从这个出发到达边权之和最大的点v,则(u, v)一定会被选中。我们知道,树的直径有这样的性质:若树中只有正边权,则从任意点出发到达最远的点一定是直径的一端。因此,只需要求出从树的两端出发到达所有点的距离,每个点对应最大生成树中被选中的边就是这两个距离的最大值。

以下的代码用三次dfs求出了树的直径的两端、从直径两端出发到达所有点的距离。时间复杂度O(n + m)

#include <bits/stdc++.h>
int read() {
	int x(0); bool fl(0); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) fl = ch == '-';
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	return fl ? -x : x;
}
const int N = 1e6 + 10, M = 2e6 + 10;
int head[N], next[M], ver[M], edge[M], tot;
void add(int u, int v, int w) {
	edge[++tot] = w;
	ver[tot] = v;
	next[tot] = head[u];
	head[u] = tot;
}
long long dist[2][N], ans_min, ans_max;
void dfs(int u, int &ans, long long *dist, int fa = 0) {
	for (int i(head[u]); i; i = next[i]) {
		int &v(ver[i]);
		if (v == fa) continue;
		dist[v] = dist[u] + edge[i];
		if (dist[v] > dist[ans]) ans = v;
		dfs(v, ans, dist, u);
	}
}
signed main() {
	std::ios::sync_with_stdio(false);
	int n(read()), st(0), ed(0);
	for (int i(1); i < n; i++) {
		int u = read(), v = read(), w = read();
		add(u, v, w), add(v, u, w);
		ans_min += w;
	}
	dfs(1, st, dist[0]);
	memset(dist[0], 0, sizeof dist[0]);
	dfs(st, ed, dist[0]);
	dfs(ed, st, dist[1]);
	for (int i(1); i <= n; i++) if (i != st) 
		ans_max += std::max(dist[0][i], dist[1][i]);
	std::cout << ans_min << ' ' << ans_max << '\n';
	return 0;
}

琼玉牌 (qiongyu)

零一串 (string)

子序列 (sequence)

小结

wrhaco大佬的题解