题解：P11379 [GESP202412 八级] 树上移动

ZPB2011 · 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;
}