自动搬运

查看原文

来自洛谷，原作者为

	tribool4_in chr(81)

搬运于2025-08-24 22:17:31，当前版本为作者最后更新于2021-03-20 18:16:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

似乎有很多题解用的是 离线+并查集，然而蒟蒻表示根本看不懂做法……

于是乎我打了个暴力 DFS，然后交了一通，结果就过了？？？

思路很简单，首先题目说，如果一个点 $u$ 的推荐视频中包含 $v$，必须要保证两点之间的路径的最小边长 $\ge k$。

显然，如果两点之间的路径的最小边长都 $\ge k$，则每条边长肯定都必须 $\ge k$。

因此，对于每个询问，从当前点出发进行深搜，如果当前边的长度 $< k$，则说明无法走通，否则情况数加一并继续深搜。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 5;
int n, q, cnt = 0;
vector<int> G[N];
int g[N][N]; // 其实存图可以不用邻接矩阵，不过反正空间足够，存了也没事
void dfs(int u, int fa, int k) {
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i]; int w = g[u][v];
		if (v != fa && w >= k) {
			cnt++;
			dfs(v, u, k);
		}
	}
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i < n; i++) {
		int p, q, r;
		scanf("%d%d%d", &p, &q, &r);
		G[p].push_back(q), G[q].push_back(p), g[p][q] = g[q][p] = r;
	}
	for (int i = 1; i <= q; i++) {
		int k, v;
		scanf("%d%d", &k, &v);
		cnt = 0;
		dfs(v, -1, k);
		printf("%d\n", cnt);
	}
	return 0;
}