时间限制:
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;
}