#include using namespace std; const int MAX_N = 200'000 + 5; int n; vector graph[MAX_N]; vector order_bfs(const vector &leafs) { deque q; vector power(n); vector used(n); for (int i = 0; i < n; ++i) { power[i] = graph[i].size(); used[i] = false; } for (int e: leafs) { q.emplace_back(e); used[e] = true; } vector order; while (!q.empty()) { int v = q.front(); order.emplace_back(v); q.pop_front(); for (int u: graph[v]) { if (used[u]) { continue; } power[u]--; if (power[u] <= 1) { // o-o-o vs o-o used[u] = true; q.emplace_back(u); } } } return order; } bool move_ants(const vector &order) { vector ants_amount(n, 1); set> q; vector inserted(n, false); int pointer = 0; while (true) { if (q.empty()) { if (pointer == order.size()) { break; } int v = order[pointer++]; inserted[v] = true; q.insert({ants_amount[v], v}); } pair s = *q.begin(); int a_amount = s.first, v = s.second; if (a_amount == n) { break; } int u = v; int cnt = 0; for (int uu : graph[v]) { if (ants_amount[uu] != 0) { cnt++; u = uu; } } if (a_amount > ants_amount[u] || cnt >= 2 || cnt == 0) { if (pointer == order.size()) { break; } int uu = order[pointer++]; q.insert({ants_amount[uu], uu}); inserted[uu] = true; continue; } q.erase(s); if (u == v) { assert(ants_amount[u] == n); break; } int old_au = ants_amount[u]; if (inserted[u]) { q.erase({old_au, u}); } ants_amount[u] += ants_amount[v]; ants_amount[v] = 0; if (inserted[u]) { q.insert({ants_amount[u], u}); } } bool found = false; for (int i = 0; i < n; ++i) { if (ants_amount[i] == n) { found = true; } } return found; } int main() { cin.tie(nullptr); cout.tie(nullptr); iostream::sync_with_stdio(false); cin >> n; for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; a--; b--; graph[a].emplace_back(b); graph[b].emplace_back(a); } if (n == 1) { cout << "YES\n"; return 0; } vector leafs; for (int i = 0; i < n; ++i) { if (graph[i].size() == 1) { leafs.emplace_back(i); } } vector order = order_bfs(leafs); bool success = move_ants(order); if (success) { cout << "YES\n"; } else { cout << "NO\n"; } }