自动搬运

查看原文

来自洛谷，原作者为

	ZPB2011 FACE THE FEAR,BUILD THE FUTURE || 一码归一码 || || 绿勾及以上或橙名或红名壶关 || 月计人&方块人 || 杀关ing误杀私信

搬运于2025-08-24 23:06:51，当前版本为作者最后更新于2024-12-11 17:30:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

树上移动

前言

为啥题解都那么复杂啊

思路

在看到数据大小后剋发现 $n$ 非常的小，于是可以考虑一个非常暴力的算法。

可以直接对每个点做一次 dfs，算出每个点可以到的最远的点，取最大值即可。

AC code

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e3 + 5;

int n, k, maxn, col[N];
vector<int> g[N];

void dfs(int u, int fa, int cnt1, int cnt2) {
	if(cnt2 > k) return;//比k大了 
	maxn = max(maxn, cnt1);
	for(int i = 0; i < g[u].size(); i++) {
		int v = g[u][i];
		if(v != fa) {
			if(col[v] == 1) dfs(v, u, cnt1 + 1, cnt2 + 1);
			else dfs(v, u, cnt1 + 1, cnt2);
		}
	} 
}

int main() {
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> col[i];
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i = 1; i <= n; i++) {//暴力遍历 
		if(col[i] == 1) dfs(i, 0, 1, 1);
		else dfs(i, 0, 1, 0);
	}
	cout << maxn << endl;
	return 0;
}