#include "testlib.h" #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define forn(i, n) for (int i = 0; i < int(n); i++) using namespace std; int leader(vector& dsu, int idx) { return dsu[idx] == idx ? dsu[idx] : (dsu[idx] = leader(dsu, dsu[idx])); } bool merge(vector& dsu, int a, int b) { a = leader(dsu, a); b = leader(dsu, b); if (a == b) return false; else { if (rnd.next(2) == 0) dsu[a] = b; else dsu[b] = a; return true; } } int main(int argc, char* argv[]) { registerValidation(argc, argv); int n = inf.readInt(2, 100000, "n"); inf.readEoln(); vector> adj(n, vector()); vector dsu(n); forn(i, n) dsu[i] = i; set > edges; forn(i, n - 1) { int x = inf.readInt(1, n, "x_i"); inf.readSpace(); int y = inf.readInt(1, n, "y_i"); inf.readEoln(); ensuref(x != y, "Tree can't contain loops"); ensuref(edges.count(make_pair(x, y)) == 0, "Tree can't contain multiple edges between a pair of vertices"); edges.insert(make_pair(x, y)); edges.insert(make_pair(y, x)); ensuref(merge(dsu, x - 1, y - 1), "Tree can't contain cycles"); adj[x - 1].push_back(y - 1); adj[y - 1].push_back(x - 1); } inf.readEof(); vector lst; for (int i = 0; i < n; i++) { if (adj[i].size() >= 3) { lst.push_back(i); } } if (lst.size() >= 2) { cout << "No" << endl; } else if (lst.size() == 0) { cout << "Yes" << endl; } else { set lens; queue>> que; que.push(make_pair(lst[0], make_pair(-1, 0))); while (!que.empty()) { auto data = que.front(); que.pop(); int v = data.first; int p = data.second.first; int d = data.second.second; bool isleaf = true; for (int w : adj[v]) { if (w != p) { isleaf = false; que.push(make_pair(w, make_pair(v, d + 1))); } } if (isleaf) { lens.insert(d); } } cout << (lens.size() == 1 ? "Yes" : "No") << endl; } }