#include using namespace std; #define debug(x) cerr << #x << ": " << x << endl #define debugArray(x, n) \ for (long long hoge = 0; (hoge) < (n); ++(hoge)) \ cerr << #x << "[" << hoge << "]: " << x[hoge] << endl template struct Tree_DP { struct Edge { int to; E data; T dp, ndp; }; using F = function; using G1 = function; using G2 = function; private: vector> graph; vector subdp, dp; const T init; const F f; const G1 g1; const G2 g2; private: void dfs_sub(int idx, int par) { for (auto &e : graph[idx]) { if (e.to == par) continue; dfs_sub(e.to, idx); subdp[idx] = f(subdp[idx], g1(subdp[e.to], e.data)); } subdp[idx] = g2(subdp[idx], idx); } void dfs_all(int idx, int par, const T &top) { T buff{init}; for (int i = 0; i < (int)graph[idx].size(); i++) { auto &e = graph[idx][i]; e.ndp = buff; e.dp = g1(par == e.to ? top : subdp[e.to], e.data); buff = f(buff, e.dp); } dp[idx] = g2(buff, idx); buff = init; for (int i = (int)graph[idx].size() - 1; i >= 0; i--) { auto &e = graph[idx][i]; if (e.to != par) dfs_all(e.to, idx, f(e.ndp, buff)); e.ndp = f(e.ndp, buff); buff = f(buff, e.dp); } } public: Tree_DP(int V, const F f, const G1 g1, const G2 g2, T init) : graph(V), f(f), g1(g1), g2(g2), init(init), subdp(V, init), dp(V, init) {} void add_edge(int u, int v, E d, E e) { graph[u].emplace_back((Edge){v, d, init, init}); graph[v].emplace_back((Edge){u, e, init, init}); } void add_edge(int u, int v, E d = E()) { add_edge(u, v, d, d); } T build(int root) { dfs_sub(root, -1); return subdp[root]; } vector build_rerooting() { dfs_sub(0, -1); dfs_all(0, -1, init); return dp; } }; signed main() { cin.tie(0); ios::sync_with_stdio(0); int N; cin >> N; using Pii = pair; auto f = [](const Pii &vdp, const Pii &chdp) { Pii ret = vdp; ret.first += max(chdp.first - 1, chdp.second); ret.second += max(chdp.first, chdp.second); return ret; }; auto g1 = [](const Pii &dp, int dat) { return dp; }; auto g2 = [](const Pii &dp, int v) { return Pii{dp.first + 1, dp.second}; }; Tree_DP graph(N, f, g1, g2, {0, 0}); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--, v--; graph.add_edge(u, v); } auto ans = graph.build(0); cout << max(ans.first, ans.second) << endl; return 0; }