#include using namespace std; #define rep(i, a, b) for(int i = a; i < (b); i++) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair pii; typedef vector vi; int main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); int N; cin >> N; vector> graph(N); vector> ograph(N); rep(i, 0, N-1) { int a, b; cin >> a >> b; a--; b--; graph[a].insert(b); graph[b].insert(a); ograph[a].insert(b); ograph[b].insert(a); } if (N == 1) { cout << "YES" << endl; return 0; } vi unblocked_leaves; vector> blocked_leaves_at(N); vi population(N, 1); rep(i, 0, N) { if (sz(graph[i]) == 1) { unblocked_leaves.push_back(i); } } while (sz(unblocked_leaves) > 0) { int l = unblocked_leaves[sz(unblocked_leaves)-1]; unblocked_leaves.pop_back(); //cerr << "moving " << l << endl; int par = *graph[l].begin(); population[par] += population[l]; population[l] = 0; graph[par].erase(l); if (population[par] == N) { cout << "YES" << endl; return 0; } if (sz(graph[par]) == 1) { if (population[*graph[par].begin()] >= population[par]) { unblocked_leaves.push_back(par); } else { blocked_leaves_at[*graph[par].begin()].insert(make_pair(population[par],par)); } } while (sz(blocked_leaves_at[par]) > 0 && blocked_leaves_at[par].begin()->first <= population[par]) { auto [npop, neigh] = *blocked_leaves_at[par].begin(); //assert(npop == population[neigh]); //assert(sz(graph[neigh]) == 1); blocked_leaves_at[par].erase(make_pair(npop, neigh)); unblocked_leaves.push_back(neigh); } } /* rep(i, 0, N) { int numneigh = 0; int maxneighpop = 0; for(int n : ograph[i]) { if (population[n] > 0) numneigh++; maxneighpop = max(maxneighpop, population[n]); } assert((population[i] == 0) + (numneigh > 1) + (maxneighpop < population[i]) == 1); } */ cout << "NO" << endl; }