solution

極端な例としてstar graphを眺め(典型)てるとなにか見えてくるのでいい感じにやる。$O(N)$。

$1$点の周囲に$n$点生えたstar graph $S_n$を考えると、必要なアンテナは$n - 1$本である。 $S_n$と$S_m$を適当な葉で繋ぐと、必要なアンテナは$n + m - 1$本。 一般に部分グラフとしてstar $S_n$を含むと、その周囲でおよそ$n - 1$本要求される。 また逆に、そのような部分グラフ以外はアンテナの本数にあまり影響しない。 具体的には次数$2$の頂点はすべて縮約してしまってよく、位相的な性質だけ考えればよいことが分かる。 そんな感じで次数$3$以上の頂点とその接続関係だけを抜き出してみよう。 これができれば雰囲気で立つ簡単な式で答えが求まる。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using namespace std;

int solve(int n, const vector<vector<int> > & g) {
    vector<vector<int> > h(n);
    function<int (int, int, int)> go = [&](int i, int parent, int ancestor) {
        if (g[i].size() == 1) {
            return -1;
        } else if (g[i].size() == 2) {
            for (int j : g[i]) if (j != parent) {
                return go(j, i, ancestor);
            }
            assert (false);
        } else {
            if (ancestor != -1) {
                h[i].push_back(ancestor);
            }
            for (int j : g[i]) if (j != parent) {
                int k = go(j, i, i);
                if (k != -1) {
                    h[i].push_back(k);
                }
            }
            return i;
        }
    };

    assert (n >= 2);
    int root = 0;
    while (root < n and g[root].size() < 3) {
        ++ root;
    }
    if (root == n) {
        return 1;
    }
    go(root, -1, -1);

    int cnt = 0;
    REP (i, n) if (g[i].size() >= 3) {
        cnt += max(0, (int)g[i].size() - (int)h[i].size() - 1);
    }
    return cnt;
}

int main() {
    // input
    int n; cin >> n;
    vector<vector<int> > g(n);
    REP (i, n - 1) {
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    // solve
    int answer = solve(n, g);

    // output
    cout << answer << endl;
    return 0;
}