「CF911F」Tree Destruction

传送门

Luogu

解题思路

显然的贪心策略，因为每次都要尽量使得删点后的收益最大。

我们可以求出树的直径（因为树上的任意一个节点与其距离最远的点一定是直径的端点）。

然后我们对于所有不是直径上的点，从叶子开始，从下往上删点，最后再由深而浅删掉直径。

最后输出答案即可。

细节注意事项

有些地方的计算不要写错式子之类的

参考代码

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <cctype>

#include <cmath>

#include <ctime>

#include <queue>

#define rg register

using namespace std;

template < typename T > inline void read(T& s) {

 	s = 0; int f = 0; char c = getchar();

 	while (!isdigit(c)) f |= (c == '-'), c = getchar();

 	while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();

 	s = f ? -s : s;

}

typedef long long LL;

const int _ = 200010;

const int __ = 400010;

int tot, head[_], nxt[__], ver[__];

inline void Add_edge(int u, int v)

{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; } 

int n, rt, lf, mark[_], fa[_], dep[_];

queue < pair < int, int > > Q;

inline void dfs1(int u, int f) {

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i]; if (v == f) continue;

		dep[v] = dep[u] + 1, dfs1(v, u);

	}

}

inline void dfs2(int u, int f) {

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i]; if (v == f) continue;

		fa[v] = u, dfs2(v, u), mark[u] |= mark[v];

	}

}

LL ans = 0;

inline void dfs3(int u, int f, int lca) {

	for (rg int i = head[u]; i; i = nxt[i]) {

		int v = ver[i]; if (v == f) continue;

		dfs3(v, u, mark[v] ? v : lca);

	}

	if (!mark[u]) {

		if (dep[u] > dep[u] + dep[lf] - 2 * dep[lca])

			ans += dep[u], Q.push(make_pair(rt, u));

		else

			ans += dep[u] + dep[lf] - 2 * dep[lca], Q.push(make_pair(lf, u));

	}

}

int main() {

#ifndef ONLINE_JUDGE

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

#endif

	read(n);

	for (rg int u, v, i = 1; i < n; ++i)

		read(u), read(v), Add_edge(u, v), Add_edge(v, u);

	dep[1] = 0, dfs1(1, 0);

	rt = 1;

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

		if (dep[i] > dep[rt]) rt = i;

	dep[rt] = 0, dfs1(rt, 0);

	lf = rt;

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

		if (dep[i] > dep[lf]) lf = i;

	mark[lf] = 1;

	dfs2(rt, 0);

	dfs3(rt, 0, rt);

	for (rg int i = lf; i != rt; i = fa[i])

		ans += dep[i], Q.push(make_pair(rt, i));

	printf("%lld\n", ans);

	while (!Q.empty()) {

		pair < int, int > x = Q.front(); Q.pop();

		printf("%d %d %d\n", x.first, x.second, x.second);

	}

	return 0;

}

完结撒花 \(qwq\)

巴特西

「CF911F」Tree Destruction

解题思路

细节注意事项

参考代码

最新文章

热门文章