#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) { bool move_ants(const vector &leafs) { vector ants_amount(n, 1); vector power(n); for (int i = 0; i < n; ++i) { power[i] = graph[i].size(); } set> q; for (auto e : leafs) { q.insert({1, e}); } while (true) { if (q.empty()) { break; // if (pointer == order.size()) { // break; // } // int v = order[pointer++]; // 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]) { break; // 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) { break; } int old_au = ants_amount[u]; if (q.count({old_au, u}) == 1) { q.erase({old_au, u}); } ants_amount[u] += ants_amount[v]; ants_amount[v] = 0; for (auto nei : graph[v]) { power[nei]--; if (power[nei] <= 1 && ants_amount[nei] != 0) { q.insert({ants_amount[nei], nei}); } } // if (inserted[u]) { // q.erase({old_au, u}); // } // 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(leafs); // bool success = move_ants(order); if (success) { cout << "YES\n"; } else { cout << "NO\n"; } }