#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef vector vl; typedef vector> vvl; typedef pair P; #define rep(i, n) for(ll i = 0; i < n; i++) #define exrep(i, a, b) for(ll i = a; i <= b; i++) #define out(x) cout << x << endl #define exout(x) printf("%.10f\n", x) #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define pb push_back #define re0 return 0 const ll mod = 1000000007; const ll INF = 1e16; struct Edge { ll to, cost; Edge(ll to, ll cost): to(to), cost(cost) {} }; vector> G; vl sz; // sz[v] : vを根とする部分木のサイズ void dfs(ll v, ll p = -1) { for(Edge e : G[v]) { if(e.to == p) { continue; } dfs(e.to, v); sz[v] += sz[e.to]; } } int main() { ll n; cin >> n; G.resize(n); vl deg(n); rep(i, n-1) { ll a, b; cin >> a >> b; a--; b--; G[a].emplace_back(b, 1); G[b].emplace_back(a, 1); deg[a]++; deg[b]++; } ll root = -1; ll ma = -1; rep(v, n) { if(ma < deg[v]) { root = v; ma = deg[v]; } } sz.assign(n, 1); dfs(root); vl dist(n, -1); // dist[v] : 頂点vの根からの距離 queue Q; dist[root] = 0; Q.push(root); while(!Q.empty()) { ll v = Q.front(); Q.pop(); for(Edge e : G[v]) { if(dist[e.to] == -1) { dist[e.to] = dist[v] + e.cost; Q.push(e.to); } } } vl dist1(n, -1); // dist1[v] : 頂点vの頂点0からの距離 queue Q1; dist1[0] = 0; Q1.push(0); while(!Q1.empty()) { ll v = Q1.front(); Q1.pop(); for(auto p : G[v]) { ll u = p.to; ll cost = p.cost; if(dist1[u] != -1) { continue; } dist1[u] = dist1[v] + cost; Q1.push(u); } } ll vertex1 = 0; // 頂点0からの距離が最大の頂点 rep(v, n) { if(dist1[vertex1] < dist1[v]) { vertex1 = v; } } vl dist2(n, -1); // dist2[v] : 頂点vの頂点vertex1からの距離 queue Q2; dist2[vertex1] = 0; Q2.push(vertex1); while(!Q2.empty()) { ll v = Q2.front(); Q2.pop(); for(auto p : G[v]) { ll u = p.to; ll cost = p.cost; if(dist2[u] != -1) { continue; } dist2[u] = dist2[v] + cost; Q2.push(u); } } ll vertex2 = vertex1; // 頂点vertex1からの距離が最大の頂点 ll TreeDiameter = 0; // 木の直径 rep(v, n) { if(dist2[vertex2] < dist2[v]) { vertex2 = v; TreeDiameter = dist2[v]; } } bool ok = true; ll x = -1; rep(v, n) { if(v != root && deg[v] == 1) { if(x == -1) { x = dist[v]; } else if(x != dist[v]) { ok = false; } } } set st; for(Edge e : G[root]) { st.insert(sz[e.to]); } if(st.size() > 1) { ok = false; } if(TreeDiameter == n-1) { ok = true; } if(ok) { out("Yes"); } else { out("No"); } re0; }