#include using namespace std; typedef long long ll; typedef unsigned long long ull; #define REP(i, n) for(int i=0; ibool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b G[100100]; void dfs(int v, int par, auto& dp){ dp[v][1] = 1; dp[v][0] = 0; using T = tuple; vector tmp; for(auto& nv : G[v]){ if(nv == par) continue; dfs(nv, v, dp); dp[v][0] += max(dp[nv][0], dp[nv][1]); dp[v][1] += dp[nv][0]; tmp.push_back(T(dp[nv][1] - dp[nv][0], dp[nv][0], dp[nv][1])); } if((int)tmp.size() > 0){ sort(tmp.rbegin(), tmp.rend()); ll val = 0; val += get<2>(tmp[0]); REPi(i,1,(int)tmp.size()){ val += get<1>(tmp[i]); } chmax(dp[v][1], val); } } int main(){ ll N; cin >> N; REP(i,N-1){ ll u, v; cin >> u >> v; u--, v--; G[u].push_back(v); G[v].push_back(u); } vector> dp(N, vector(2)); dfs(0, -1, dp); ll ans = max(dp[0][0], dp[0][1]); cout << ans << endl; return 0; }