Advertisement
KuanTall

Untitled

Jan 15th, 2023
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.60 KB | Food | 0 0
  1. 2-3
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. class Node{
  7. public:
  8. int index;
  9. Node *adj1;
  10. Node *adj2;
  11. Node *adj3;
  12. bool joint;
  13. Node *left;
  14. Node *right;
  15. int length1;
  16. int length2;
  17.  
  18. Node(int a):index(a), adj1(0), adj2(0), adj3(0), joint(false), left(0), right(0), length1(0), length2(0){};
  19. Node():index(0), adj1(0), adj2(0), adj3(0), joint(false), left(0), right(0), length1(0), length2(0){};
  20. };
  21.  
  22. void connectNode(Node* a, Node* b){
  23. if(a->adj1 == 0)
  24. a->adj1 = b;
  25. else if(a->adj2 == 0)
  26. a->adj2 = b;
  27. else if(a->adj3 == 0){
  28. a->adj3 = b;
  29. a->joint = true;
  30. }
  31.  
  32. if(b->adj1 == 0)
  33. b->adj1 = a;
  34. else if(b->adj2 == 0)
  35. b->adj2 = a;
  36. else if(b->adj3 == 0){
  37. b->adj3 = a;
  38. b->joint = true;
  39. }
  40. }
  41.  
  42. void findOtherJoint(Node* node, Node* cur){
  43. int length = 0;
  44. Node* last = node;
  45. while(1){
  46. length++;
  47. if(cur == 0){
  48. if(node->length1 == 0)
  49. node->length1 = length-1;
  50. else
  51. node->length2 = length-1;
  52. return;
  53. }
  54. if(cur->joint == true){
  55. if(node->left == 0){
  56. node->left = cur;
  57. return;
  58. }
  59. else{
  60. node->right = cur;
  61. return;
  62. }
  63. }
  64.  
  65. if(cur->adj1 == last){
  66. last = cur;
  67. cur = cur->adj2;
  68. }
  69. else if(cur->adj2 == last){
  70. last = cur;
  71. cur = cur->adj1;
  72. }
  73. }
  74. }
  75.  
  76. void joint_and_length(Node* node){
  77. Node* cur = new Node();
  78.  
  79. cur = node->adj1;
  80. findOtherJoint(node, cur);
  81. cur = node->adj2;
  82. findOtherJoint(node, cur);
  83. cur = node->adj3;
  84. findOtherJoint(node, cur);
  85. }
  86.  
  87. int main()
  88. {
  89. int n, m;
  90. int a, b;
  91. vector<Node*> nodes;
  92. vector<int> joints;
  93. vector<int> Ckey, Dkey, DkeyR;
  94. //cin
  95. cin>>n;
  96. for(int i = 0 ; i < n ; i++){
  97. nodes.push_back(new Node(i));
  98. }
  99. for(int i = 0 ; i < n-1 ; i++){
  100. cin>>a>>b;
  101. connectNode(nodes[a], nodes[b]);
  102. }
  103. cin>>m;
  104. for(int i = 0 ; i < m ; i++){
  105. cin>>a;
  106. Ckey.push_back(a);
  107. }
  108. //make Dkey
  109. for(int i = 0 ; i < (int)nodes.size() ; i++){
  110. if(nodes[i]->joint == true)
  111. joints.push_back(i);
  112. }
  113. if((int)joints.size() != (int)Ckey.size()){
  114. cout<<"NO";
  115. return 0;
  116. }
  117. for(int i = 0 ; i < (int)joints.size() ; i++){
  118. joint_and_length(nodes[joints[i]]);
  119. }
  120. for(int i = 0 ; i < (int)joints.size() ; i++){
  121. if(nodes[joints[i]]->left == 0 || nodes[joints[i]]->right == 0){
  122. swap(joints[0], joints[i]);
  123. break;
  124. }
  125. }
  126.  
  127. for(int i = 0 ; i < (int)joints.size() ; i++){
  128. for(int j = i+1 ; j < (int)joints.size() ; j++){
  129. if(nodes[joints[j]]->left == nodes[joints[i]] || nodes[joints[j]]->right == nodes[joints[i]]){
  130. swap(joints[j], joints[i+1]);
  131. break;
  132. }
  133. }
  134. }
  135. Dkey.resize(joints.size());
  136. DkeyR.resize(joints.size());
  137. for(int i = 1 ; i < (int)joints.size()-1 ; i++){
  138. Dkey[i] = nodes[joints[i]]->length1;
  139. DkeyR[DkeyR.size()-1-i] = nodes[joints[i]]->length1;
  140. }
  141.  
  142. Dkey[0] = nodes[joints[0]]->length1;
  143. Dkey[Dkey.size()-1] = nodes[joints[joints.size()-1]]->length1;
  144. DkeyR[0] = nodes[joints[joints.size()-1]]->length1;
  145. DkeyR[Dkey.size()-1] = nodes[joints[0]]->length1;
  146. if(Dkey == Ckey || DkeyR == Ckey){
  147. cout<<"YES";
  148. return 0;
  149. }
  150. Dkey[0] = nodes[joints[0]]->length2;
  151. Dkey[Dkey.size()-1] = nodes[joints[joints.size()-1]]->length1;
  152. DkeyR[0] = nodes[joints[joints.size()-1]]->length1;
  153. DkeyR[Dkey.size()-1] = nodes[joints[0]]->length2;
  154. if(Dkey == Ckey || DkeyR == Ckey){
  155. cout<<"YES";
  156. return 0;
  157. }
  158. Dkey[0] = nodes[joints[0]]->length1;
  159. Dkey[Dkey.size()-1] = nodes[joints[joints.size()-1]]->length2;
  160. DkeyR[0] = nodes[joints[joints.size()-1]]->length2;
  161. DkeyR[Dkey.size()-1] = nodes[joints[0]]->length1;
  162. if(Dkey == Ckey || DkeyR == Ckey){
  163. cout<<"YES";
  164. return 0;
  165. }
  166. Dkey[0] = nodes[joints[0]]->length2;
  167. Dkey[Dkey.size()-1] = nodes[joints[joints.size()-1]]->length2;
  168. DkeyR[0] = nodes[joints[joints.size()-1]]->length2;
  169. DkeyR[Dkey.size()-1] = nodes[joints[0]]->length2;
  170. if(Dkey == Ckey || DkeyR == Ckey){
  171. cout<<"YES";
  172. return 0;
  173. }
  174. cout<<"NO";
  175.  
  176. return 0;
  177. }
Tags: e04
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement