#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define rep(i,n) for(int i=0; i<(n); i++) #define FOR(i,x,n) for(int i=x; i<(n); i++) #define vint(a,n) vint a(n); rep(i, n) cin >> a[i]; #define vll(a,n) vll a(n); rep(i, n) cin >> a[i]; #define ALL(n) begin(n),end(n) #define RALL(n) rbegin(n),rend(n) #define MOD (1000000007) // #define MOD (998244353) #define INF (1e9+7) #define INFL (2e18) typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; using vint=vector; using vll=vector; using vbool=vector; using P=pair; templateusing arr=vector>; templateint popcount(T &a){int c=0; rep(i, 8*(int)sizeof(a)){if((a>>i)&1) c++;} return c;} templatevoid pl(T x){cout << x << " ";} templatevoid pr(T x){cout << x << endl;} template inline void pr(T Tar, Ts... ts) { std::cout << Tar << " "; pr(ts...); return; } templatevoid prvec(vector& a){rep(i, (int)a.size()-1){pl(a[i]);} pr(a.back());} templatevoid prarr(arr& a){rep(i, (int)a.size()) if(a[i].empty()) pr(""); else prvec(a[i]);} templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b void Fill(A (&array)[N], const T &val){fill( (T*)array, (T*)(array+N), val );} // dijkstra法。ただし、全ての枝の距離が1のとき、BFS void dijkstra(int st, arr

& G, vll& dist, vbool& seen, bool is_all_one=false){ int V = G.size(); priority_queue, greater

> min_heap; min_heap.push({0, st}); dist.assign(V, INFL); seen.assign(V, false); dist[st] = 0; // 全ての枝の距離が1なら、単純なbfsで求められる。 if(is_all_one){ queue que; que.push(st); seen[st] = true; while(!que.empty()){ int now = que.front(); que.pop(); ll d = dist[now]; for(auto p: G[now]){ int nx = p.second; if(seen[nx]) continue; seen[nx] = true; dist[nx] = d + 1; que.push(nx); } } return; } int frm; ll d; while(!min_heap.empty()){ tie(d, frm) = min_heap.top(); min_heap.pop(); if(seen[frm]) continue; // printf("node=%d", frm); seen[frm] = true; dist[frm] = d; for(P e: G[frm]){ if(dist[e.second] > d+e.first) min_heap.push({d+e.first, e.second}); // printf("(%d, %d) pushed", d+e.first, e.second); } } } int main() { int n; cin >> n; arr g(n); vint in(n, 0); int st; rep(i, n-1){ int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); in[a]++; in[b]++; } vint v; rep(i, n) { if(in[i]==1) v.push_back(i); } if(v.size()==2){ pr("Yes"); return 0; } st = v[0]; vint par(n, -1); queue que; que.push(st); int dist = 0; while(!que.empty()){ int now = que.front(); que.pop(); for(int nx: g[now]){ if(par[now]==nx) continue; par[nx] = now; que.push(nx); } } // prvec(par); vint depth(n, -1); rep(i, n){ if(in[i]>1) continue; if(i==st) continue; que.push(i); depth[i] = 0; } int ans = -1; while(!que.empty()){ int now = que.front(); que.pop(); int p = par[now]; int d = depth[now]; if(p==-1) { if(ans!=-1 && d != ans){ pr("No"); return 0; } continue; } if(depth[p]==-1){ depth[p] = d+1; que.push(p); }else{ if(depth[p] != d+1){ pr("No"); return 0; }else if(ans!=-1){ int t = (d+1)*2; if(ans != t){ pr("No"); return 0; } } ans = (d+1)*2; } } // prvec(depth); pr("Yes"); return 0;}