#include using namespace std; typedef long long ll; typedef long double ld; typedef pair ii; typedef vector vi; typedef vector vvi; typedef vector vii; #define x first #define y second #define pb push_back #define eb emplace_back #define rep(i,a,b) for(auto i = (a); i < (b); ++i) #define REP(i,n) rep(i,0,n) #define all(v) begin(v), end(v) #define sz(v) ((int) (v).size()) #define rs resize vector> buren; vector grootte; ll bepaalGrootte(ll x, ll p){ ll som = 1; ll buur; for(ll y = 0; y < buren[x].size();y++){ buur = buren[x][y]; if(buur != p){ som += bepaalGrootte(buur, x); } } grootte[x] = som; return som; } bool mogelijk(ll x, ll p)//Is het mogelijk om alle mieren behalve uit p in x te verzamelen? { //Ga langs lopen wie we allemaal hebben vector extra; ll buur; for(ll y = 0; y< buren[x].size();y++){ buur = buren[x][y]; if(buur != p){ if(!mogelijk(buur, x)){ return false; } extra.push_back(grootte[buur]); } } //Kijk of het kan sort(extra.begin(),extra.end()); ll som = 1; for(ll y = 0; y < extra.size();y++){ if(extra[y] > som){ return false; } som += extra[y]; } return true; } signed main(){ ll n; cin>>n; for(ll x= 0; x< n;x++){ vector vec; buren.push_back(vec); grootte.push_back(-1); } ll a, b; for(ll x=0;x> a; cin>>b; a--; b--; buren[a].push_back(b); buren[b].push_back(a); } //Zet het begin klaar grootte[0] = n; for(ll x=0; x < buren[0].size();x++){ bepaalGrootte(buren[0][x],0); } //Bepaal waar we heen lopen ll eind = 0; ll groot, buur; while(true){ groot = -1; for(ll x=0; x < buren[eind].size();x++){ buur = buren[eind][x]; if(grootte[buur] > n / 2){ groot = buur; break; } } if(groot == -1){ break; } grootte[eind] = n - grootte[groot]; grootte[groot] = n; eind = groot; } //Test vervolgens of het mogelijk is if(mogelijk(eind, -1)){ cout << "YES" << endl; } else{ cout << "NO" << endl; } return 0; }