自动搬运

查看原文

来自洛谷，原作者为

	Mr_罗 π⁴+π⁵≈e⁶ | Per Aspera Ad Astra | トゲナシトゲアリ > MyGO!!!!!

搬运于2025-08-24 21:57:28，当前版本为作者最后更新于2021-08-27 10:31:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$Part 0$：前言

这是本蒟蒻的第一篇题解，求赞 & 求管理员大大通过 $\text{QAQ}$

$Part 1$：读题

题目要求：Bessie 在一棵根为 $K$ 号节点的树根上，要求在叶子节点上放置农民并最小化农民数量（农民可移动），使和农民速度相同的 Bessie 在不接触到农民的前提下无法走到任意一个叶子节点。真简洁

$Part 2$：初步理清思路

思路一：硬怼！

就像 大佬 @bessie_goes_moo 的思路 那样，直接模拟题意。

预计时间复杂度：$\text{O}(ans \times n)$

最大时间复杂度：$\text{O}(n^2)$

好像能被卡掉（雾

思路二：正解

就是给每一个叶子节点放一个农民，让他们和 Bessie 一起走，看看 Bessie 能遇到几个人。

这里借用一下 @llzzxx712 大佬的图 （我懒得画）：

我们先给每个叶子节点安排一个农民：

（橙点为农民）

然后让农民一直往上走，直到遇到 会影分身的 Bessie，这里就是他们能控制的点：

（红点为农民可控制的点）

然后开始 dfs，让 Bessie 开始走。Bessie 遇到了两个红点，说明只需要两个农民就可以锁住 Bessie 了（在节点 $9 \ (10)$ 和节点 $17$ ）。

同理，我们也可以模拟一下样例。鉴于篇幅有限，我放在了 云剪贴板 里面，大家可自行观看。

$Part 3$：深入思考，获得代码思路

大概思路一有，代码的思路也就出来了：在每一个被农民控制的点做一个标记，再遍历整棵树，遇到标记就 $\text{ans}$ 加一。最后输出 $\text{ans}$ 即可。

$Part 4$：代码

这里我提供 $3$ 种不同的标记实现方式：

1. 在第一遍遍历的时候记录下每个结点的父亲节点，再单独从每个叶子节点向上反，做标记。

2. 在第一遍遍历的时候用一个栈记录路径，每次找到叶子节点就在 $($栈顶的位置 $\times \ \dfrac{1}{2}$ $)$ 处的节点做标记。

3. 在第一遍遍历的时候记录一个 $\text{down}$ 数组表示离这里最近的叶子节点的距离。在第二遍遍历的时候，如果当前的深度 $\ge$ 当前节点的 $\text{down}$ 值，就算遇到了标记。

---

方式 $1$ 的代码：

#include <bits/stdc++.h>
using namespace std;

int n, k, a, b, l, fa[100001], dep[100001] = {-1}, ans;
bool leaf[100001], flag[100001];
vector<int> tree[100001];

void dfs1 (int i, int fr)
{
	leaf[i] = 1;
	fa[i] = fr;
	dep[i] = dep[fr] + 1;
	for (int k = 0; k < tree[i].size(); k++)
	{
		int now = tree[i][k];
		if (now != fr)
		{
			leaf[i] = 0;
			dfs1 (now, i);
		}
	}
}

void dfs2 (int i, int fr)
{
	if (flag[i])
	{
		ans++;
		return;
	}
	for (int k = 0; k < tree[i].size(); k++)
	{
		int now = tree[i][k];
		if (now != fr)
			dfs2 (now, i);
	}
}


int main()
{
	cin >> n >> k;
	fa[k] = 0;
	for (int i = 1; i < n; i++)
	{
		cin >> a >> b;
		tree[a].push_back (b);
		tree[b].push_back (a);
	}
	dfs1 (k, 0);
	for (int i = 1; i <= n; i++)
	{
		if (leaf[i])
		{
			int dis = i;
			for (int j = 1; j <= dep[i] / 2; j++)
				dis = fa[dis];
			flag[dis] = 1;
		}
	}
	dfs2 (k, 0);
	cout << ans;
	return 0;
}

提交记录

---

方式 $2$ 的代码：

#include <bits/stdc++.h>
using namespace std;

int n, k, a, b, l, st[100001], top, fa[100001], dep[100001] = {-1}, ans;
bool leaf[100001], flag[100001];
vector<int> tree[100001];

void dfs1 (int i, int fr)
{
	st[++top] = i;
	if (tree[i].size() == 1)
	{
		flag[st[top / 2 + 1]] = 1;
		top--;
		return;
	}
	for (int k = 0; k < tree[i].size(); k++)
	{
		int now = tree[i][k];
		if (now != fr)
			dfs1 (now, i);
	}
	top--;
}

void dfs2 (int i, int fr)
{
	if (flag[i])
	{
		ans++;
		return;
	}
	for (int k = 0; k < tree[i].size(); k++)
	{
		int now = tree[i][k];
		if (now != fr)
			dfs2 (now, i);
	}
}


int main()
{
	cin >> n >> k;
	fa[k] = 0;
	for (int i = 1; i < n; i++)
	{
		cin >> a >> b;
		tree[a].push_back (b);
		tree[b].push_back (a);
	}
	dfs1 (k, 0);
	dfs2 (k, 0);
	cout << ans;
	return 0;
}

提交记录

---

方案 $3$ 的代码：

#include <bits/stdc++.h>
using namespace std;

int n, k, a, b, down[100001], ans;
vector<int> tree[100001];

void dfs1 (int i, int fr)
{
	down[i] = 0x7fffffff;
	if (tree[i].size() == 1)
		down[i] = 0;
	
	for (int k = 0; k < tree[i].size(); k++)
	{
		int now = tree[i][k];
		if (now != fr)
		{
			dfs1 (now, i);
			down[i] = min (down[now] + 1, down[i]);
		}
	}
}

void dfs2 (int i, int fr, int deep)
{
	if (deep >= down[i])
	{
		ans++;
		return;
	}
	for (int k = 0; k < tree[i].size(); k++)
	{
		int now = tree[i][k];
		if (now != fr)
			dfs2 (now, i, deep + 1);
	}
}


int main()
{
	cin >> n >> k;
	for (int i = 1; i < n; i++)
	{
		cin >> a >> b;
		tree[a].push_back (b);
		tree[b].push_back (a);
	}
	dfs1 (k, 0);
	dfs2 (k, 0, 0);
	cout << ans;
	return 0;
}

提交记录

---

完结撒花~~~