1 条题解

  • 0
    @ 2023-12-12 19:09:22
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1505;
    int n, f[maxn][2];
    vector<int> g[maxn];
    
    void dfs(int u, int p) {
        f[u][1] = 1;
        for (auto v : g[u]) {
            if (v != p) {
                dfs(v, u);
                f[u][0] += f[v][1];
                f[u][1] += min(f[v][0], f[v][1]);
            }
        }
    }
    
    int main() {
        cin >> n;
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        dfs(1, -1);
        cout << min(f[1][0], f[1][1]);
        return 0;
    }
    
    
    • 1

    信息

    ID
    63
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    7
    已通过
    2
    上传者