Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.91 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const int SIZE = (int)1e5 + 1;
  9. const int INF = (int)1e9;
  10. int max_dist = 0;
  11. int max_v = 1;
  12.  
  13. vector<int> ans1[SIZE];
  14. vector<int> ans2[SIZE];
  15. int tree[SIZE];
  16. vector<int> g[SIZE];
  17. int dist[SIZE];
  18. int dist2[SIZE];
  19. int head;
  20. vector<int> vertex;
  21.  
  22. int bfs(int v, bool flag) {
  23. fill(dist, dist + SIZE, INF);
  24. dist[v] = 0;
  25. queue<int> q;
  26. q.push(v);
  27. while (!q.empty()) {
  28. v = q.front();
  29. q.pop();
  30. for (int i = 0; i < (int)g[v].size(); i++) {
  31. if (dist[g[v][i]] > dist[v] + 1) {
  32. dist[g[v][i]] = dist[v] + 1;
  33. q.push(g[v][i]);
  34. if (max_dist <= dist[g[v][i]]) {
  35. max_dist = max(max_dist, dist[g[v][i]]);
  36. max_v = g[v][i];
  37. }
  38. if (flag && dist[g[v][i]] == dist2[g[v][i]]) {
  39. head = g[v][i];
  40. }
  41. }
  42. }
  43. }
  44. return max_v;
  45. }
  46.  
  47. void dfs(int v, int depth, vector<int> ans[SIZE]) {
  48. dist[v] = 1;
  49. if ((int)g[v].size() == 0) {
  50. tree[v] = 1;
  51. }
  52. for (int i = 0; i < (int)g[v].size(); i++) {
  53. if (dist[g[v][i]] == 0) {
  54. dfs(g[v][i], depth + 1, ans);
  55. tree[v] += tree[g[v][i]];
  56. ans[depth].push_back(tree[g[v][i]]);
  57. }
  58. }
  59. }
  60.  
  61.  
  62. int main() {
  63. ios_base::sync_with_stdio(0);
  64. cin.tie(0);
  65. cout.tie(0);
  66.  
  67. int n;
  68. cin >> n;
  69. for (int i = 0; i < n - 1; i++) {
  70. int a, b;
  71. cin >> a >> b;
  72. g[a].push_back(b);
  73. g[b].push_back(a);
  74. }
  75.  
  76. if (n % 2 == 0) {
  77. cout << "NO\n";
  78. return 0;
  79. }
  80.  
  81. int v = 1;
  82. for (int i = 0; i < 2; i++) {
  83. v = bfs(v, 0);
  84. }
  85.  
  86.  
  87.  
  88. for (int i = 1; i < n + 1; i++) {
  89. if (dist[i] == max_dist / 2 && g[i].size() == 2) {
  90. vertex.push_back(i);
  91. }
  92. }
  93.  
  94. for (int j = 0; j < SIZE; j++) {
  95. dist2[j] = dist[j];
  96. }
  97.  
  98. bfs(v, 1);
  99.  
  100. if ((int)g[head].size() != 2) {
  101. cout << "NO\n";
  102. return 0;
  103. }
  104.  
  105. fill(dist, dist + SIZE, 0);
  106. fill(tree, tree + SIZE, 0);
  107. dist[head] = 1;
  108. dfs(g[head][0], 0, ans1);
  109. dfs(g[head][1], 0, ans2);
  110.  
  111. for (int i = 0; i < SIZE; i++) {
  112. sort(ans1[i].begin(), ans1[i].end());
  113. sort(ans2[i].begin(), ans2[i].end());
  114. }
  115.  
  116. bool flag = 1;
  117.  
  118. for (int i = 0; i < SIZE; i++) {
  119. if (flag == 0 || ans1[i].size() != ans2[i].size()) {
  120. flag = 0;
  121. break;
  122. }
  123.  
  124. for (int j = 0; j < (int)ans1[i].size(); j++) {
  125. if (ans1[i][j] != ans2[i][j]) {
  126. flag = 0;
  127. break;
  128. }
  129. }
  130. }
  131.  
  132. if (flag) {
  133. cout << "YES\n";
  134. } else {
  135. cout << "NO\n";
  136. }
  137. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement