Code

#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;
}

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

vector<int> subtree_size;

void dfs(vector<vector<int>> &adj, int src, int par = -1) {
    subtree_size[src] = 1;
    for (auto child : adj[src]) {
        if (child != par) {
            dfs(adj, child, src);
            subtree_size[src] += subtree_size[child];
        }
    }
}

int solve(vector<vector<int>> &adj) {
    int n = adj.size();

    subtree_size.clear();
    subtree_size.resize(n);

    dfs(adj, 0);
    int biggest_child_size_of_root = 0;
    for (auto child : adj[0]) {
        biggest_child_size_of_root =
            max(biggest_child_size_of_root, subtree_size[child]);
    }

    return n - biggest_child_size_of_root;
}

int main() {
    int n;
    cin >> n;

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

    cout << solve(adj) << "\n";
}