#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); vector where_to_move(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; where_to_move[v] = v; int cnt = 0; for (int u: graph[v]) { if (ants_amount[u] != 0) { where_to_move[v] = u; cnt++; } } if (cnt >= 2) { cnt = 0; for (int u: graph[v]) { if (!inserted[u]) { where_to_move[v] = u; cnt++; } } if (cnt >= 2) { break; } } q.insert({ants_amount[v], v}); } pair s = *q.begin(); int a_amount = s.first, v = s.second; if (a_amount == n) { break; } if (a_amount > ants_amount[where_to_move[v]]) { if (pointer == order.size()) { break; } int u = order[pointer++]; q.insert({ants_amount[u], u}); inserted[u] = true; where_to_move[u] = u; int cnt = 0; for (int uu: graph[u]) { if (ants_amount[uu] != 0) { where_to_move[u] = uu; cnt++; } } if (cnt >= 2) { cnt = 0; for (int uu: graph[u]) { if (!inserted[uu]) { where_to_move[u] = uu; cnt++; } } if (cnt >= 2) { break; } } continue; } q.erase(s); int u = where_to_move[v]; assert(u != -1); 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"; } }