#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int MAX_V = 500000; vector _E[MAX_V]; struct Edge { int to; ll cost; Edge(int to = -1, ll cost = -1) { this->to = to; this->cost = cost; } }; vector E[MAX_V]; struct Node { int v; ll cost; Node(int v = -1, ll cost = -1) { this->v = v; this->cost = cost; } }; class Tree { public: int nodeCnt; Tree(int nodeCnt = MAX_V) { this->nodeCnt = nodeCnt; } void addEdge(int from, int to, ll cost = 1) { E[from].push_back(Edge(to, cost)); } vector diameter(int from = 0) { int u = findFarthestVertex(from); int v = findFarthestVertex(u); return findPath(u, v); } ll calcPathCost(vector &path) { ll totalCost = 0; for (int i = 0; i < path.size() - 1; ++i) { int u = path[i]; int v = path[i + 1]; for (int j = 0; j < E[u].size(); ++j) { if (E[u][j].to == v) { totalCost += E[u][j].cost; } } } return totalCost; } vector findPath(int from, int to) { queue que; que.push(Node(from, 0)); int parent[nodeCnt]; bool visited[nodeCnt]; memset(visited, false, sizeof(visited)); while (!que.empty()) { Node node = que.front(); que.pop(); visited[node.v] = true; if (node.v == to) { vector path; int cur = node.v; while (cur != from) { path.push_back(cur); cur = parent[cur]; } path.push_back(from); reverse(path.begin(), path.end()); return path; } for (int i = 0; i < E[node.v].size(); ++i) { Edge edge = E[node.v][i]; if (visited[edge.to]) continue; parent[edge.to] = node.v; que.push(Node(edge.to, node.cost + edge.cost)); } } return vector(); } private: int findFarthestVertex(int from) { queue que; que.push(Node(from, 0)); bool visited[MAX_V]; memset(visited, false, sizeof(visited)); ll maxCost = INT_MIN; int farthestV = -1; while (!que.empty()) { Node node = que.front(); que.pop(); if (visited[node.v]) continue; visited[node.v] = true; if (maxCost < node.cost) { maxCost = node.cost; farthestV = node.v; } for (int i = 0; i < E[node.v].size(); ++i) { Edge edge = E[node.v][i]; Node next(edge.to, node.cost + edge.cost); que.push(next); } } return farthestV; } }; int main() { int N; cin >> N; Tree tree; int a, b, c; for (int i = 0; i < N - 1; ++i) { cin >> a >> b; --a; --b; _E[a].push_back(b); _E[b].push_back(a); tree.addEdge(a, b, 1); tree.addEdge(b, a, 1); } vector path = tree.diameter(); queue que; queue d_que; bool visited[N]; memset(visited, false, sizeof(visited)); que.push(path[0]); d_que.push(1); fprintf(stderr, "path size: %d\n", (int) path.size()); while (not que.empty()) { int v = que.front(); int d = d_que.front(); que.pop(); d_que.pop(); if (visited[v]) continue; visited[v] = true; if (d > 1 && _E[v].size() == 1 && path.size() != d) { cout << "No" << endl; return 0; } for (int u : _E[v]) { que.push(u); d_que.push(d + 1); } } memset(visited, false, sizeof(visited)); que.push(path.back()); d_que.push(1); while (not que.empty()) { int v = que.front(); int d = d_que.front(); que.pop(); d_que.pop(); if (visited[v]) continue; visited[v] = true; if (d > 1 && _E[v].size() == 1 && path.size() != d) { cout << "No" << endl; return 0; } for (int u : _E[v]) { que.push(u); d_que.push(d + 1); } } cout << "Yes" << endl; return 0; }