/* -*- coding: utf-8 -*- * * 1424.cc: No.1424 Ultrapalindrome - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; /* typedef */ typedef vector vi; /* global variables */ vi nbrs[MAX_N]; int ps[MAX_N], ds[MAX_N], cis[MAX_N]; /* subroutines */ /* main */ int main() { int n; scanf("%d", &n); for (int i = 1; i < n; i++) { int a, b; scanf("%d%d", &a, &b); a--, b--; nbrs[a].push_back(b); nbrs[b].push_back(a); } int ln = 0, rt = -1; for (int u = 0; u < n; u++) { int szu = nbrs[u].size(); if (szu == 1) ln++; else if (szu > 2) { if (rt < 0) rt = u; else { puts("No"); return 0; } } } if (ln == 2) { puts("Yes"); return 0; } int ld = -1; ps[rt] = -1, ds[rt] = 0; for (int u = rt; u >= 0;) { vi &nbru = nbrs[u]; int &ciu = cis[u]; if (ciu < nbru.size() && nbru[ciu] == ps[u]) ciu++; if (ciu < nbru.size()) { int v = nbru[ciu++]; ps[v] = u, ds[v] = ds[u] + 1; if (nbrs[v].size() == 1) { if (ld < 0) ld = ds[v]; else if (ld != ds[v]) { puts("No"); return 0; } } u = v; } else { u = ps[u]; } } puts("Yes"); return 0; }