题解

思路分析

这是一道 树上BFS + 点分治 + 贪心 的博弈问题。

问题建模

• 树有 $N$ 个节点，叶子节点是出口
• Bessie 从节点 $i$ 出发逃跑
• 农民在叶子节点等待
• 求抓住 Bessie 的最少农民数

核心思路

1. 关键观察

Bessie 从节点 $i$ 出发，农民从叶子出发，双方都走最短路。

如果某个叶子 $L$ 到节点 $i$ 的距离 $\leq$ Bessie 到 $L$ 的距离，则这个叶子需要放农民。

2. BFS 预处理

从所有叶子节点同时开始 BFS（多源BFS）：

• $dist[i]$ = 从任意叶子到节点 $i$ 的最短距离

3. 点分治统计

对于每个询问节点 $i$，需要统计：

• 有多少个叶子 $L$ 满足：$d(L, i) \leq dist[i]$

使用点分治优化统计：

• 分治中心为 $rt$
• 对于子树中的点，统计满足条件的叶子数

4. 容斥原理

使用容斥计算：

算法步骤

1. 多源BFS：

   • 从所有叶子同时 BFS
   • 预处理 $dist[i]$

2. 点分治：

   • 找重心进行分治
   • 对每个子树统计贡献

3. 排序 + 双指针：

   • 按距离排序
   • 使用双指针统计满足条件的叶子

4. 输出答案

复杂度分析

• BFS：$O(N)$
• 点分治：$O(N \log N)$
• 总时间复杂度：$O(N \log N)$
• 空间复杂度：$O(N)$

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 2e5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int n, rt, cnt;
int head[N + 5], ver[M + 5], nxt[M + 5], deg[N + 5], tot;
int vis[N + 5], dist[N + 5];
int c[N + 5];
int sz[N + 5], son[N + 5];
int ans[N + 5], dep[N + 5];
queue<int> que;

void addedge(int x, int y) {
	ver[++tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
	deg[y]++;
}

void pre() {
	for (int i = 1; i <= n; i++) {
		if (deg[i] == 1) {
			dist[i] = 0;
			vis[i] = 1;
			que.push(i);
		}
	}
	while (!que.empty()) {
		int x = que.front();
		que.pop();
		for (int i = head[x]; i != -1; i = nxt[i]) {
			int y = ver[i];
			if (vis[y]) {
				continue;
			}
			vis[y] = 1;
			que.push(y);
			dist[y] = dist[x] + 1;
		}
	}
	memset(vis, 0, sizeof vis);
}

void get_rt(int x, int fa) {
	sz[x] = 1;
	son[x] = 0;
	for (int i = head[x]; i != -1; i = nxt[i]) {
		int y = ver[i];
		if (y == fa || vis[y]) {
			continue;
		}
		get_rt(y, x);
		sz[x] += sz[y];
		son[x] = max(son[x], sz[y]);
	}
	son[x] = max(son[x], cnt - sz[x]);
	if (son[x] < son[rt]) {
		rt = x;
	}
}

int nums;

struct Point {
	int idx, dist;
	bool friend operator < (Point p, Point q) {
		return p.dist < q.dist;
	}
}p[N + 5];

struct Node {
	int g, c;
	bool friend operator < (Node p, Node q) {
		return p.g < q.g;
	}	
}q[N + 5];


void get_dep(int x, int fa, int d) {
	dep[x] = d;
	for (int i = head[x]; i != -1; i = nxt[i]) {
		int y = ver[i];
		if (y == fa || vis[y]) {
			continue;
		}
		get_dep(y, x, d + 1);
	}
}

void dfs(int x, int fa) {
	++nums;
	p[nums] = (Point){x, dep[x]};
	q[nums] = (Node){dist[x] - dep[x], 2 - deg[x]};
	for (int i = head[x]; i != -1; i = nxt[i]) {
		int y = ver[i];
		if (y == fa || vis[y]) {
			continue;
		}
		dfs(y, x);
	}
}

void calc(int x, int fa, int f) {
	nums = 0;
	dfs(x, fa);
	sort(p + 1, p + nums + 1);
	sort(q + 1, q + nums + 1);
	int pos = 0, sum = 0;
	for (int i = 1; i <= nums; i++) {
		while (pos + 1 <= nums && p[i].dist >= q[pos + 1].g) {
			sum += q[pos + 1].c;
			pos++;
		}
		ans[p[i].idx] += sum * f;
	}
}

void solve(int x) {
	vis[x] = 1;
	get_dep(x, 0, 0);
	calc(x, 0, 1);
	for (int i = head[x]; i != -1; i = nxt[i]) {
		int y = ver[i];
		if (vis[y]) {
			continue;
		}
		calc(y, x, -1);
		cnt = sz[y];
		rt = 0;
		get_rt(y, x);
		solve(rt);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	memset(head, -1, sizeof head);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		addedge(x, y);
		addedge(y, x);
	}
	pre();
	rt = 0;
	cnt = son[0] = n;
	get_rt(1, 0);
	solve(rt);
	for (int i = 1; i <= n; i++) {
		if (deg[i] == 1) {
			ans[i] = 1;
		}
		cout << ans[i] << "\n";
	}
	return 0;
}

题解

把所有叶子同时作为源点做一次 BFS，得到 dist[u]——农民最快从某个出口赶到结点 u 所需要的时间。显然，如果 Bessie 在向某个出口前进的途中遇到一个点 v 满足 dist[v] ≤ depth_x(v)（depth_x(v) 是她从起点 x 走到 v 的步数），那么在那个时刻农民就能截住她。因此，对每个起点 x，我们只需要统计有多少个出口的路径上会出现这样的“拦截节点”。

直接枚举所有起点会达到 O(n^2)，因此我们使用点分治。每次取一棵子树的重心 c 作为切分点，计算所有经过 c 的路径对答案的贡献，然后再向各个儿子递归。对于某个重心 c，我们 DFS 得到它子树中所有结点的深度 dep[u] 以及 dist[u]−dep[u] 的值：前者表示 Bessie 经过的时间，后者表示农民从某个出口赶到 u 的“剩余余量”。只要 dist[u] ≤ dep[u]，说明在 Bessie 抵达 u 前农民一定能到达该点，于是与之同路径的所有入口都必须安排农民。

为了在一遍遍历中快速统计贡献，我们把结点按 dep[u] 从小到大排序，同时把 (dist[u]−dep[u]) 以及它对应能阻断多少条出口路径的信息排序维护。在扫描过程中，用一个指针维护已经满足 dist[v]−dep[v] ≤ dep[u] 的节点数；对于这些节点关联的出口路径，每出现一次就说明需要在该出口安排一个农民，从而给所有当前扫描的结点增加 1。子树贡献算完之后，我们再对每个儿子做一次减法，以免路径被重复统计，然后继续递归点分治。

最终得到的 ans[i] 就是从结点 i 出发时，最少需要安排的农民数量。对于本来就是出口的结点，还需要把答案强制为 1——只要在该出口安排一名农民即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 2e5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int n, rt, cnt;
int head[N + 5], ver[M + 5], nxt[M + 5], deg[N + 5], tot;
int vis[N + 5], dist[N + 5];
int c[N + 5];
int sz[N + 5], son[N + 5];
int ans[N + 5], dep[N + 5];
queue<int> que;

void addedge(int x, int y) {
	ver[++tot] = y;
	nxt[tot] = head[x];
	head[x] = tot;
	deg[y]++;
}

void pre() {
	for (int i = 1; i <= n; i++) {
		if (deg[i] == 1) {
			dist[i] = 0;
			vis[i] = 1;
			que.push(i);
		}
	}
	while (!que.empty()) {
		int x = que.front();
		que.pop();
		for (int i = head[x]; i != -1; i = nxt[i]) {
			int y = ver[i];
			if (vis[y]) {
				continue;
			}
			vis[y] = 1;
			que.push(y);
			dist[y] = dist[x] + 1;
		}
	}
	memset(vis, 0, sizeof vis);
}

void get_rt(int x, int fa) {
	sz[x] = 1;
	son[x] = 0;
	for (int i = head[x]; i != -1; i = nxt[i]) {
		int y = ver[i];
		if (y == fa || vis[y]) {
			continue;
		}
		get_rt(y, x);
		sz[x] += sz[y];
		son[x] = max(son[x], sz[y]);
	}
	son[x] = max(son[x], cnt - sz[x]);
	if (son[x] < son[rt]) {
		rt = x;
	}
}

int nums;

struct Point {
	int idx, dist;
	bool friend operator < (Point p, Point q) {
		return p.dist < q.dist;
	}
}p[N + 5];

struct Node {
	int g, c;
	bool friend operator < (Node p, Node q) {
		return p.g < q.g;
	}	
}q[N + 5];


void get_dep(int x, int fa, int d) {
	dep[x] = d;
	for (int i = head[x]; i != -1; i = nxt[i]) {
		int y = ver[i];
		if (y == fa || vis[y]) {
			continue;
		}
		get_dep(y, x, d + 1);
	}
}

void dfs(int x, int fa) {
	++nums;
	p[nums] = (Point){x, dep[x]};
	q[nums] = (Node){dist[x] - dep[x], 2 - deg[x]};
	for (int i = head[x]; i != -1; i = nxt[i]) {
		int y = ver[i];
		if (y == fa || vis[y]) {
			continue;
		}
		dfs(y, x);
	}
}

void calc(int x, int fa, int f) {
	nums = 0;
	dfs(x, fa);
	sort(p + 1, p + nums + 1);
	sort(q + 1, q + nums + 1);
	int pos = 0, sum = 0;
	for (int i = 1; i <= nums; i++) {
		while (pos + 1 <= nums && p[i].dist >= q[pos + 1].g) {
			sum += q[pos + 1].c;
			pos++;
		}
		ans[p[i].idx] += sum * f;
	}
}

void solve(int x) {
	vis[x] = 1;
	get_dep(x, 0, 0);
	calc(x, 0, 1);
	for (int i = head[x]; i != -1; i = nxt[i]) {
		int y = ver[i];
		if (vis[y]) {
			continue;
		}
		calc(y, x, -1);
		cnt = sz[y];
		rt = 0;
		get_rt(y, x);
		solve(rt);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	memset(head, -1, sizeof head);
	cin >> n;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		addedge(x, y);
		addedge(y, x);
	}
	pre();
	rt = 0;
	cnt = son[0] = n;
	get_rt(1, 0);
	solve(rt);
	for (int i = 1; i <= n; i++) {
		if (deg[i] == 1) {
			ans[i] = 1;
		}
		cout << ans[i] << "\n";
	}
	return 0;
}