题解 | 小O的叶子

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> g(n + 1);
    vector<int> deg(n + 1, 0);
    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
        ++deg[u]; ++deg[v];
    }
    // 初始叶子数（度为1）
    int L = 0;
    for (int i = 1; i <= n; ++i) if (deg[i] == 1) ++L;
    long long ans = 0;
    for (int v = 1; v <= n; ++v) {
        int c1 = 0, c2 = 0;               // 叶子邻居个数、原度为2的邻居个数
        for (int u : g[v]) {
            if (deg[u] == 1) ++c1;
            else if (deg[u] == 2) ++c2;
        }
        long long cur = (long long)L - (deg[v] == 1) - c1 + c2;
        ans = max(ans, cur);
    }
    cout << ans << '\n';
    return 0;
}