#include using namespace std; const int MAX_N = 200'000 + 5; int n; vector graph[MAX_N]; vector> depth; vector depth_bfs(const vector &leafs) { deque q; vector power(n); for (int i = 0; i < n; ++i) { power[i] = graph[i].size(); } for (auto e : leafs) { q.emplace_back(e); depth[e] = {0, e}; } vector order; while (!q.empty()) { int v = q.front(); order.emplace_back(v); q.pop_front(); for (int u : graph[v]) { if (depth[u].first != -1) { continue; } power[u]--; if (power[u] <= 1) { // o-o-o vs o-o depth[u] = {depth[v].first + 1, u}; q.emplace_back(u); } } } return order; } vector where_to_move; void place_where_to_move(const vector &order) { vector rev_order(n); for (int i = 0; i < n; ++i) { rev_order[order[i]] = i; } for (int v = 0; v < n; ++v) { int cur_cand = -1; int cur_val = -1; for (int u : graph[v]) { if (rev_order[u] > cur_val) { cur_val = rev_order[u]; cur_cand = u; } } where_to_move[v] = cur_cand; } } vector ants_amount; void move_ants(const vector &order) { set> q; // vector power(n); vector inserted(n); for (int i = 0; i < n; ++i) { // power[i] = graph[i].size(); inserted[i] = 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 > ants_amount[where_to_move[v]]) { if (pointer == order.size()) { break; } while (pointer < order.size()) { int u = order[pointer++]; q.insert({ants_amount[u], u}); inserted[u] = true; if (ants_amount[u] < a_amount) { break; } } continue; } q.erase(s); int u = where_to_move[v]; 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}); } } } int main() { cin.tie(nullptr); cout.tie(nullptr); iostream::sync_with_stdio(false); cin >> n; depth.resize(n, {-1, -1}); ants_amount.resize(n, 1); where_to_move.resize(n, -1); 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 = depth_bfs(leafs); place_where_to_move(order); move_ants(order); bool success = true; int counts_n = 0; for (int i = 0; i < n; ++i) { if (ants_amount[i] == 0) continue; if (ants_amount[i] == n) {counts_n++; continue;} success = false; break; } if (success && counts_n == 1) { cout << "YES\n"; } else { cout << "NO\n"; } }