#include #include using namespace std; struct Tree { int n; int r; int l; std::vector> prit; std::vector> t; std::vector par; std::vector dpt; std::vector tour; std::vector> appear_on_tour; std::vector> anc; Tree(){} Tree(int n, int r) : n(n), r(r){ prit.resize(n); t.resize(n); par.resize(n); dpt.resize(n); } void add_edge(int u, int v){ prit[u].push_back(v); prit[v].push_back(u); } void build(int r_){ r = r_; for(int i = 0; i < n; i++) t[i].clear(); for(int i = 0; i < n; i++) dpt[i] = -1; std::queue que; par[r] = -1; dpt[r] = 0; que.push(r); while(que.size()){ int u = que.front(); que.pop(); for(int v : prit[u]){ if(dpt[v] == -1){ t[u].push_back(v); par[v] = u; dpt[v] = dpt[u] + 1; que.push(v); } } } } /* std::vector toposort(){ std::vector> p(n); for(int i = 0; i < n; i++) p[i] = std::pair(dpt[i], i); sort(p.begin(), p.end(), std::greater>()); std::vector res(n); for(int i = 0; i < n; i++) res[i] = p[i].second; return res; } */ void dfs(int u, int &k){ appear_on_tour[u].push_back(k); tour[k++] = u; for(int v : t[u]){ dfs(v, k); appear_on_tour[u].push_back(k); tour[k++] = u; } } void build_euler_tour(){ tour.resize(n * 2 - 1); appear_on_tour.resize(n); int k = 0; dfs(0, k); } void build_lca(){ for(l = 1; l <= n; l++){ if((1 << (l - 1)) >= n) break; } anc.resize(l); for(int j = 0; j < l; j++) anc[j].resize(n); for(int i = 0; i < n; i++) anc[0][i] = par[i]; for(int j = 1; j < l; j++){ for(int i = 0; i < n; i++){ if(anc[j - 1][i] == -1) anc[j][i] = -1; else anc[j][i] = anc[j - 1][anc[j - 1][i]]; } } } int lca(int u, int v){ if(dpt[u] < dpt[v]) std::swap(u, v); int dpt_diff = dpt[u] - dpt[v]; for(int j = l - 1; j >= 0; j--){ if((dpt_diff >> j) & 1) u = anc[j][u]; } if(u == v) return u; for(int j = l - 1; j >= 0; j--){ if(anc[j][u] != anc[j][v]){ u = anc[j][u]; v = anc[j][v]; } } return anc[0][u]; } }; int main() { int n; cin >> n; Tree t(n, 0); int d[100005]{0}; for(int i = 0; i < n - 1; i++){ int a, b; cin >> a >> b; a--; b--; d[a]++; d[b]++; t.add_edge(a, b); } int r = -1; for(int i = 0; i < n; i++){ if(d[i] >= 3){ if(r == -1) r = i; else{ cout << "No" << endl; return 0; } } } if(r == -1){ cout << "Yes" << endl; return 0; } t.build(r); int s = -1; for(int i = 0; i < n; i++){ if((int)t.t[i].size() == 0){ if(s == -1) s = t.dpt[i]; else if(s != t.dpt[i]){ cout << "No" << endl; return 0; } } } cout << "Yes" << endl; }