Advertisement
Guest User

Untitled

a guest
Aug 29th, 2015
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.67 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long LL;
  4. int n;
  5. vector<int> e[110000];
  6. int vis[110000];
  7. int no = 0;
  8. // 0 = point
  9. // 1 = side from both points
  10. // 2 = halfplane
  11. // 3 = double halfplane from 1
  12. // 4 = double halfplane from side
  13. // 5 = plane
  14. int dfs(int a){
  15. if(vis[a]) return -1;
  16. //cout << a << endl;
  17. vis[a] = 1;
  18. int n[6];
  19. for(int i = 0; i < 6; i++) n[i] = 0;
  20. for(int i = 0; i < e[a].size(); i++){
  21. int r = dfs(e[a][i]);
  22. if(r >= 0){
  23. n[r]++;
  24. //cout << e[a][i] << " " << r << endl;
  25. }
  26. }
  27. if(n[5] >= 1){
  28. no = 1;
  29. return 5;
  30. }
  31. if(n[3] + n[4] >= 2){
  32. no = 1;
  33. return 5;
  34. }
  35. if(n[2]*(n[3]+n[4]) >= 1){
  36. no = 1;
  37. return 5;
  38. }
  39. if(n[2] >= 3){
  40. no = 1;
  41. return 5;
  42. }
  43. if(n[4] == 1){
  44. if(n[3] +n[2]+n[1]>= 1){
  45. no = 1;
  46. return 5;
  47. }
  48. if(n[0] >= 2){
  49. no = 1;
  50. return 5;
  51. }
  52. if(n[0] == 1){
  53. return 5;
  54. }
  55. if(n[0] == 0){
  56. return 4;
  57. }
  58. }
  59. if(n[3] == 1){
  60. if(n[2]+n[1]>= 1){
  61. no = 1;
  62. return 5;
  63. }
  64. if(n[0] >= 3){
  65. no = 1;
  66. return 5;
  67. }
  68. if(n[0] == 2){
  69. return 5;
  70. }
  71. return 4;
  72. }
  73. if(n[2] == 2){
  74. return 3;
  75. }
  76. if(n[2] == 1){
  77. return 2;
  78. }
  79. if(n[1] >= 1){
  80. return 2;
  81. }
  82. if(n[0] >= 3){
  83. return 2;
  84. }
  85. if(n[0] >= 2){
  86. return 1;
  87. }
  88. return 0;
  89. }
  90. int main(){
  91. cin >> n;
  92. int r = 0;
  93. for(int i = 1; i < n; i++){
  94. int a, b; cin >> a >> b;
  95. a--; b--;
  96. e[a].push_back(b);
  97. e[b].push_back(a);
  98. vis[i] = 0;
  99. }
  100. for(int i = 0; i < n; i++){
  101. if(e[i].size() == 1){
  102. r = i;
  103. }
  104. }
  105. dfs(r);
  106. for(int i = 0; i < n; i++){
  107. //cout << dfs(i) << endl;
  108. }
  109. if(no == 1){
  110. cout << "No" << endl;
  111. } else {
  112. cout << "Yes" << endl;
  113. }
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement