#include using namespace std; using ll = long long; using ld = long double; struct record{ int ant_amount; int vertex_number; int neighbor_amount; }; int main(){ int n; cin >> n; vector ants(n,1); vector> neighbors(n); vector neigh_amounts(n,0); for(int i = 0; i < n-1; i++){ int u,v; cin >> u >> v; u--; v--; neighbors[u].push_back(v); neighbors[v].push_back(u); neigh_amounts[u]++; neigh_amounts[v]++; } auto before = [](record a, record b) { if(a.ant_amount < b.ant_amount){ return false; } if(a.ant_amount > b.ant_amount){ return true; } return a.neighbor_amount > b.neighbor_amount; }; priority_queue, decltype(before)> q(before); for(int i = 0; i < n; i++){ record to_add; to_add.ant_amount = 1; to_add.vertex_number = i; to_add.neighbor_amount = neighbors[i].size(); q.push(to_add); } bool ok = true; while(q.size()){ record top = q.top(); q.pop(); //check if actual int ants_v = top.ant_amount; int v = top.vertex_number; int size = top.neighbor_amount; if(size != neigh_amounts[v]){ continue; } if(ants_v != ants[v]){ continue; } //check if leaf (bad otherwise) if(size > 1){ ok = false; break; } //move everyone to neighbor and update ant amount and neighbor amounts ants[v] = 0; int only_neighbor = -1; for(int i : neighbors[v]){ if(ants[i] > 0){ only_neighbor = i; break; } } if(only_neighbor == -1){ break; } ants[only_neighbor] += ants_v; neigh_amounts[only_neighbor]--; //push updated record record to_add; to_add.ant_amount = ants[only_neighbor]; to_add.vertex_number = only_neighbor; to_add.neighbor_amount = neigh_amounts[only_neighbor]; q.push(to_add); } if(ok){ cout << "YES"; }else{ cout << "NO"; } cout << endl; }