2023/8/11题解

时间限制:

1000MS

内存限制:

65536KB

解题思路

建树 + 模拟 ，复杂在于建树，此处从题目需求可知需要按层建树，所以需要队列模拟，查找比较容易就是普通的深搜

参考代码

#include<bits/stdc++.h>
using namespace std;
vector<int> v;
vector<int> a;
vector<int> b;
int n,q,num;
int cnt = 1;
const int N = 1e5 + 10;
class node{public:int val;vector<node*> chil;node(int num){val = num;}
};vector<node*> mp(N,nullptr);node *root = nullptr;void build(node *head){if(!head){return;}queue<node*> que;que.push(head);while(!que.empty()){int len = que.size();for(int k = 0; k < len; ++k){head = que.front();que.pop();int i = cnt - 2;int begin = v[i];while(i < n - 1 && begin == v[i++]){node *t = new node(cnt);mp[cnt++] = t;head->chil.push_back(t);}for(node* z : head->chil){que.push(z);}}}}int find(node *p){if(!p){return 1;}int s = 0;for(node *i : p->chil){s += find(i);}return s == 0 ? 1 : s;
}void debug(node* head){if(!head){return;}queue<node*> que;que.push(head);while(!que.empty()){      int len = que.size();for(int k = 0; k < len; ++k){node* p = que.front();que.pop();cout << p->val << ' ';for(node* i : p->chil){que.push(i);}}cout << endl;}return;
}int main(){root = new node(cnt);mp[cnt++] = root;cin >> n >> q;for(int i = 0; i < n - 1; ++i){cin >> num;v.push_back(num);}sort(v.begin(), v.end());build(root);
//   debug(root);for(int i = 0; i < q; ++i){cin >> num;a.push_back(num);}for(int i = 0; i < q; ++i){cin >> num;b.push_back(num);}int res = 0;for(int i = 0 ; i < q; ++i){int res_a = find(mp[a[i]]);int res_b = find(mp[b[i]]);// cout << res_a << ' ' << res_b << endl;res ^= res_a * res_b;}cout << res;return 0;
}