Submission #48962744

---

Source Code Expand

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

class Tree {
  public:
    int n;
    vector<int> tin, tout;
    vector<vector<int>> adj;
    int timer = 0;
    Tree(int n) {
        this->n = n;
        adj.resize(n);
        tin.resize(n);
        tout.resize(n);
    }

  public:
    void dfs(int src, int par) {
        tin[src] = ++timer;
        for (auto child : adj[src]) {
            if (child != par) {
                dfs(child, src);
            }
        }
        tout[src] = ++timer;
    }
};

void solve() {
    int n;
    cin >> n;
    Tree t(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        t.adj[u].push_back(v);
        t.adj[v].push_back(u);
    }

    t.dfs(0, -1);
    vector<int> child_subtree_sizes_of_root;
    for (auto child : t.adj[0]) {
        int sz = (t.tout[child] - t.tin[child] + 1) / 2;
        child_subtree_sizes_of_root.push_back(sz);
    }

    sort(child_subtree_sizes_of_root.begin(),
         child_subtree_sizes_of_root.end());
    child_subtree_sizes_of_root.pop_back();
    cout << 1 + accumulate(child_subtree_sizes_of_root.begin(),
                           child_subtree_sizes_of_root.end(), 0)
         << endl;
}

int main() {
    solve();
    return 0;
}

Submission Info

Judge Result