Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- using namespace std;
- const int SIZE = (int)1e5 + 1;
- const int INF = (int)1e9;
- int max_dist = 0;
- int max_v = 1;
- vector<int> ans1[SIZE];
- vector<int> ans2[SIZE];
- int tree[SIZE];
- vector<int> g[SIZE];
- int dist[SIZE];
- int dist2[SIZE];
- int head;
- vector<int> vertex;
- int bfs(int v, bool flag) {
- fill(dist, dist + SIZE, INF);
- dist[v] = 0;
- queue<int> q;
- q.push(v);
- while (!q.empty()) {
- v = q.front();
- q.pop();
- for (int i = 0; i < (int)g[v].size(); i++) {
- if (dist[g[v][i]] > dist[v] + 1) {
- dist[g[v][i]] = dist[v] + 1;
- q.push(g[v][i]);
- if (max_dist <= dist[g[v][i]]) {
- max_dist = max(max_dist, dist[g[v][i]]);
- max_v = g[v][i];
- }
- if (flag && dist[g[v][i]] == dist2[g[v][i]]) {
- head = g[v][i];
- }
- }
- }
- }
- return max_v;
- }
- void dfs(int v, int depth, vector<int> ans[SIZE]) {
- dist[v] = 1;
- if ((int)g[v].size() == 0) {
- tree[v] = 1;
- }
- for (int i = 0; i < (int)g[v].size(); i++) {
- if (dist[g[v][i]] == 0) {
- dfs(g[v][i], depth + 1, ans);
- tree[v] += tree[g[v][i]];
- ans[depth].push_back(tree[g[v][i]]);
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- for (int i = 0; i < n - 1; i++) {
- int a, b;
- cin >> a >> b;
- g[a].push_back(b);
- g[b].push_back(a);
- }
- if (n % 2 == 0) {
- cout << "NO\n";
- return 0;
- }
- int v = 1;
- for (int i = 0; i < 2; i++) {
- v = bfs(v, 0);
- }
- for (int i = 1; i < n + 1; i++) {
- if (dist[i] == max_dist / 2 && g[i].size() == 2) {
- vertex.push_back(i);
- }
- }
- for (int j = 0; j < SIZE; j++) {
- dist2[j] = dist[j];
- }
- bfs(v, 1);
- if ((int)g[head].size() != 2) {
- cout << "NO\n";
- return 0;
- }
- fill(dist, dist + SIZE, 0);
- fill(tree, tree + SIZE, 0);
- dist[head] = 1;
- dfs(g[head][0], 0, ans1);
- dfs(g[head][1], 0, ans2);
- for (int i = 0; i < SIZE; i++) {
- sort(ans1[i].begin(), ans1[i].end());
- sort(ans2[i].begin(), ans2[i].end());
- }
- bool flag = 1;
- for (int i = 0; i < SIZE; i++) {
- if (flag == 0 || ans1[i].size() != ans2[i].size()) {
- flag = 0;
- break;
- }
- for (int j = 0; j < (int)ans1[i].size(); j++) {
- if (ans1[i][j] != ans2[i][j]) {
- flag = 0;
- break;
- }
- }
- }
- if (flag) {
- cout << "YES\n";
- } else {
- cout << "NO\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement