// Saarland University: <(OvO)> #include #define sz(a) ((int)(a).size()) #define divceil(a, b) ((a) + (b) - 1) / (b) using namespace std; #ifdef ONPC string to_string(const char* s) { return s; } template string to_string(const T& cont) { string ans = ""; for (bool fst = true; const auto& val: cont) { if (!fst) { ans += ", "; } ans += to_string(val); fst = false; } return ans + "}"; } void debug_print_collection() { cerr << endl; } template void debug_print_collection(First val, Args... args) { cerr << " " << to_string(val); debug_print_collection(args...); } #define debug(...) { cerr << "@@@ [" << #__VA_ARGS__ << "] ="; debug_print_collection(__VA_ARGS__);} #else #define debug(...) ; #define NDEBUG #endif mt19937 rnd(123); typedef long long ll; typedef long double ld; int solve() { int n; if (!(cin >> n)) { return 1; } vector> g(n); for (int i = 1; i < n; i++) { int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } vector siz(n, 0); function dfs = [&](int v, int pr) { siz[v] = 1; for (int u : g[v]) { if (u != pr) { dfs(u, v); siz[v] += siz[u]; } } }; dfs(0, -1); int r = 0, pr = -1; while (true) { int go = -1; for (int u : g[r]) { if (u != pr && siz[u] * 2 > n) { go = u; break; } } if (go == -1) { break; } pr = r; r = go; } dfs(r, -1); for (int i = 0; i < n; i++) { sort(g[i].begin(), g[i].end(), [&](int x, int y) { return siz[x] < siz[y]; }); if (i != r) { g[i].pop_back(); } int sum = 1; for (int u : g[i]) { if (sum < siz[u]) { cout << "NO\n"; return 0; } sum += siz[u]; } } cout << "YES\n"; return 0; } int32_t main() { #ifdef ONPC assert(freopen("C.txt", "r", stdin)); #endif int TET = 1e9; // cin >> TET; for (int i = 1; i <= TET; i ++) { if (solve()) { break; } #ifdef ONPC cout << "__________________" << endl; #endif } #ifdef ONPC cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; #endif } /* g++ -std=c++20 -Wall -Wextra -Wshadow -D_GLIBCXX_DEBUG -DONPC -O2 -fsanitize=address -fsanitize=undefined -fno-sanitize-recover -o ex template.cpp && ./ex */