Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 2-3
- #include<bits/stdc++.h>
- using namespace std;
- class Node{
- public:
- int index;
- Node *adj1;
- Node *adj2;
- Node *adj3;
- bool joint;
- Node *left;
- Node *right;
- int length1;
- int length2;
- Node(int a):index(a), adj1(0), adj2(0), adj3(0), joint(false), left(0), right(0), length1(0), length2(0){};
- Node():index(0), adj1(0), adj2(0), adj3(0), joint(false), left(0), right(0), length1(0), length2(0){};
- };
- void connectNode(Node* a, Node* b){
- if(a->adj1 == 0)
- a->adj1 = b;
- else if(a->adj2 == 0)
- a->adj2 = b;
- else if(a->adj3 == 0){
- a->adj3 = b;
- a->joint = true;
- }
- if(b->adj1 == 0)
- b->adj1 = a;
- else if(b->adj2 == 0)
- b->adj2 = a;
- else if(b->adj3 == 0){
- b->adj3 = a;
- b->joint = true;
- }
- }
- void findOtherJoint(Node* node, Node* cur){
- int length = 0;
- Node* last = node;
- while(1){
- length++;
- if(cur == 0){
- if(node->length1 == 0)
- node->length1 = length-1;
- else
- node->length2 = length-1;
- return;
- }
- if(cur->joint == true){
- if(node->left == 0){
- node->left = cur;
- return;
- }
- else{
- node->right = cur;
- return;
- }
- }
- if(cur->adj1 == last){
- last = cur;
- cur = cur->adj2;
- }
- else if(cur->adj2 == last){
- last = cur;
- cur = cur->adj1;
- }
- }
- }
- void joint_and_length(Node* node){
- Node* cur = new Node();
- cur = node->adj1;
- findOtherJoint(node, cur);
- cur = node->adj2;
- findOtherJoint(node, cur);
- cur = node->adj3;
- findOtherJoint(node, cur);
- }
- int main()
- {
- int n, m;
- int a, b;
- vector<Node*> nodes;
- vector<int> joints;
- vector<int> Ckey, Dkey, DkeyR;
- //cin
- cin>>n;
- for(int i = 0 ; i < n ; i++){
- nodes.push_back(new Node(i));
- }
- for(int i = 0 ; i < n-1 ; i++){
- cin>>a>>b;
- connectNode(nodes[a], nodes[b]);
- }
- cin>>m;
- for(int i = 0 ; i < m ; i++){
- cin>>a;
- Ckey.push_back(a);
- }
- //make Dkey
- for(int i = 0 ; i < (int)nodes.size() ; i++){
- if(nodes[i]->joint == true)
- joints.push_back(i);
- }
- if((int)joints.size() != (int)Ckey.size()){
- cout<<"NO";
- return 0;
- }
- for(int i = 0 ; i < (int)joints.size() ; i++){
- joint_and_length(nodes[joints[i]]);
- }
- for(int i = 0 ; i < (int)joints.size() ; i++){
- if(nodes[joints[i]]->left == 0 || nodes[joints[i]]->right == 0){
- swap(joints[0], joints[i]);
- break;
- }
- }
- for(int i = 0 ; i < (int)joints.size() ; i++){
- for(int j = i+1 ; j < (int)joints.size() ; j++){
- if(nodes[joints[j]]->left == nodes[joints[i]] || nodes[joints[j]]->right == nodes[joints[i]]){
- swap(joints[j], joints[i+1]);
- break;
- }
- }
- }
- Dkey.resize(joints.size());
- DkeyR.resize(joints.size());
- for(int i = 1 ; i < (int)joints.size()-1 ; i++){
- Dkey[i] = nodes[joints[i]]->length1;
- DkeyR[DkeyR.size()-1-i] = nodes[joints[i]]->length1;
- }
- Dkey[0] = nodes[joints[0]]->length1;
- Dkey[Dkey.size()-1] = nodes[joints[joints.size()-1]]->length1;
- DkeyR[0] = nodes[joints[joints.size()-1]]->length1;
- DkeyR[Dkey.size()-1] = nodes[joints[0]]->length1;
- if(Dkey == Ckey || DkeyR == Ckey){
- cout<<"YES";
- return 0;
- }
- Dkey[0] = nodes[joints[0]]->length2;
- Dkey[Dkey.size()-1] = nodes[joints[joints.size()-1]]->length1;
- DkeyR[0] = nodes[joints[joints.size()-1]]->length1;
- DkeyR[Dkey.size()-1] = nodes[joints[0]]->length2;
- if(Dkey == Ckey || DkeyR == Ckey){
- cout<<"YES";
- return 0;
- }
- Dkey[0] = nodes[joints[0]]->length1;
- Dkey[Dkey.size()-1] = nodes[joints[joints.size()-1]]->length2;
- DkeyR[0] = nodes[joints[joints.size()-1]]->length2;
- DkeyR[Dkey.size()-1] = nodes[joints[0]]->length1;
- if(Dkey == Ckey || DkeyR == Ckey){
- cout<<"YES";
- return 0;
- }
- Dkey[0] = nodes[joints[0]]->length2;
- Dkey[Dkey.size()-1] = nodes[joints[joints.size()-1]]->length2;
- DkeyR[0] = nodes[joints[joints.size()-1]]->length2;
- DkeyR[Dkey.size()-1] = nodes[joints[0]]->length2;
- if(Dkey == Ckey || DkeyR == Ckey){
- cout<<"YES";
- return 0;
- }
- cout<<"NO";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement