#include #include using namespace std; typedef long long int ll; struct Vertex { ll id; vector adj; ll deg; ll size = 1; }; vector graph; bool searchNode(ll id, ll parent) { if (graph[id].adj.size() == 1) { return true; } bool pos = true; for (int i = 0; i < graph[id].adj.size(); ++i) { if (graph[id].adj[i] == parent) continue; pos = pos && searchNode(graph[id].adj[i], id); } if (!pos) return false; vector childSizes; for (int i = 0; i < graph[id].adj.size(); ++i) { if (graph[id].adj[i] == parent) continue; childSizes.emplace_back(graph[graph[id].adj[i]].size); } sort(childSizes.begin(), childSizes.end()); for (int i = 0; i < childSizes.size(); ++i) { if (childSizes[i] <= graph[id].size) { graph[id].size += childSizes[i]; } else return false; } return pos; } int main() { ll n; cin >> n; graph.resize(n); for (int i = 0; i < n - 1; ++i) { ll u, v; cin >> u >> v; u--; v--; graph[u].adj.emplace_back(v); graph[v].adj.emplace_back(u); } queue curVtx; //vector visited(n); for (int i = 0; i < n; ++i) { graph[i].deg = graph[i].adj.size(); if (graph[i].deg == 1) { curVtx.push(i); //visited[i] = true; } } ll centroid = -1; while (!curVtx.empty()) { queue newQueue; while (!curVtx.empty()) { ll cur = curVtx.front(); curVtx.pop(); centroid = cur; for (ll s: graph[cur].adj) { graph[s].deg--; if (graph[s].deg == 1) { newQueue.push(s); } } } curVtx = std::move(newQueue); /*for (int i = 0; i < graph[cur].adj.size(); ++i) { ll next = graph[cur].adj[i]; if (!visited[next]) { graph[next].size += graph[cur].size; graph[next].deg--; if (graph[next].deg <= 1 && !visited[next]) { visited[next] = true; curVtx.push(next); } break; } }*/ } // cout << centroid << '\n'; bool pos = searchNode(centroid, -1); if (pos) cout << "YES" << endl; else cout << "NO" << endl; return 0; }