#include #define int long long using namespace std; string to_string(string s) { return s; } template string to_string(T v) { string res = "["; for (const auto &x : v) { res += to_string(x) + ", "; } res += "]"; return res; } void dbg_out() { cout << endl; } template void dbg_out(Head H, Tail... T) { cout << ' ' << to_string(H); dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif using ll = long long; using vi = vector; #define rep(i, a, b) for (int i = (a); i < (b); ++i) #define all(v) (v).begin(), (v).end() #define sz(v) ((int)(v).size()) const int MAX_NODES = 3e5; vector Adj[MAX_NODES]; int Sz[MAX_NODES]; int nbNodes; int DfsSz(int node, int parent = -1) { int sum = 1; for (int dest : Adj[node]) { if (dest != parent) sum += DfsSz(dest, node); } return Sz[node] = sum; } pair FindCentroid(int node, int parent = -1) { int other = -1; for (int dest : Adj[node]) { if (dest != parent && 2 * Sz[dest] > nbNodes) return FindCentroid(dest, node); if (dest != parent && 2 * Sz[dest] == nbNodes) other = dest; } return make_pair(node, other); } int DfsCheck(int node, int parent = -1) { vector sz; for (int dest : Adj[node]) { if (dest != parent) { if (!DfsCheck(dest, node)) return 0; sz.push_back(Sz[dest]); } } sort(sz.begin(), sz.end()); int sum = 1; for (int a : sz) { if (a > sum) return 0; sum += a; } return 1; } void Read() { cin >> nbNodes; for (int i = 1; i < nbNodes; i ++) { int a, b; cin >> a >> b; Adj[-- a].push_back(-- b); Adj[b].push_back(a); } DfsSz(0); pair center = FindCentroid(0, 0); int ans = 0; DfsSz(center.first); ans |= DfsCheck(center.first); if (center.second >= 0) { DfsSz(center.second); ans |= DfsCheck(center.second); } cout << (ans ? "YES" : "NO") << endl; return; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); Read(); return 0; }