#pragma GCC optimize("Ofast") #include #define rep(i,n) for(int i=0;i>x[i]; #define ft first #define sc second #define pb push_back #define lb lower_bound #define ub upper_bound #define all(v) (v).begin(),(v).end() #define LB(a,x) lb(all(a),x)-a.begin() #define UB(a,x) ub(all(a),x)-a.begin() #define mod 1000000007 //#define mod 998244353 #define FS fixed< using V=vector; using P=pair; typedef unsigned long long ull; typedef long double ldouble; template inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } template inline void out(T a){ cout << a << '\n'; } void YN(bool ok){if(ok) cout << "Yes" << endl; else cout << "No" << endl;} //void YN(bool ok){if(ok) cout << "YES" << endl; else cout << "NO" << endl;} const ll INF=1e18; const int mx=200005; class LCA{ public: V> G; int n; int root; V> par; V depth; int MX_LOG=24; explicit LCA(V> g,int sz,int root_){ G=g; n=sz; root=root_; par.resize(MX_LOG,V(n,0)); depth.resize(n,0); init(); } void dfs(int v,int p,int d){ par[0][v]=p; depth[v]=d; for(int i=0;idepth[v]) swap(u,v); for(int k=0;k>k&1){ v=par[k][v]; } } if(u==v) return u; //二分探索でLCAを求める for(int k=MX_LOG-1;k>=0;k--){ if(par[k][u]!=par[k][v]){ u=par[k][u]; v=par[k][v]; } } return par[0][u]; } ll dist(int u){ return (ll)depth[u]; } }; int main(){ //オーバーフローは大丈夫ですか?? cin.tie(0);ios::sync_with_stdio(false); int n; cin>>n; V> G(n); V deg(n,0); rep(i,n-1){ int a,b; cin>>a>>b; a--;b--; G[a].pb(b); G[b].pb(a); deg[a]++; deg[b]++; } int root; rep(i,n){ if(deg[i]>1){ root=i; break; } } V d(n,-1); queue que; que.push(root); d[root]=0; while(que.size()){ int v=que.front(); que.pop(); for(int nv:G[v]){ if(d[nv]!=-1) continue; d[nv]=d[v]+1; que.push(nv); } } set st; V cnt(n,0); V vec; rep(i,n){ if(deg[i]==1){ st.insert(d[i]); cnt[d[i]]++; vec.pb(i); } } bool ok=1; if(st.size()>2) ok=0; if(st.size()==2){ int c_u=*begin(st); int c_v=*rbegin(st); LCA lca(G,n,root); sort(all(vec),[&](auto a,auto b){ return d[a] < d[b]; }); int sz=vec.size(); set ST; int u=vec[0],v=vec[sz-1]; int z=lca.get(u,v); ST.insert(d[v]+d[u]-2*d[z]); if(cnt[c_u]>1){ int vv=vec[1]; int uu=lca.get(vv,u); ST.insert(d[vv]+d[u]-2*d[uu]); } if(cnt[c_v]>1){ int vv=vec[sz-2]; int uu=lca.get(vv,v); ST.insert(d[vv]+d[v]-2*d[uu]); } if(ST.size()>1) ok=0; } YN(ok); }