Query on A Tree
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 733 Accepted Submission(s): 275
One day, monkey A learned about one of the bit-operations, xor. He was keen of this interesting operation and wanted to practise it at once.
Monkey A gave a value to each node on the tree. And he was curious about a problem.
The problem is how large the xor result of number x and one node value of label y can be, when giving you a non-negative integer x and a node label u indicates that node y is in the subtree whose root is u(y can be equal to u).
Can you help him?
For each test case there are two positive integers n and q, indicate that the tree has n nodes and you need to answer q queries.
Then two lines follow.
The first line contains n non-negative integers V1,V2,⋯,Vn, indicating the value of node i.
The second line contains n-1 non-negative integers F1,F2,⋯Fn−1, Fi means the father of node i+1.
And then q lines follow.
In the i-th line, there are two integers u and x, indicating that the node you pick should be in the subtree of u, and x has been described in the problem.
2≤n,q≤105
0≤Vi≤109
1≤Fi≤n, the root of the tree is node 1.
1≤u≤n,0≤x≤109
3
网上有用DFS序来做的，但是本蒟蒻并不太清楚他们dalao的做法，所以只是大了一发可持久化trie合并。。
对于这一题，主要涉及trie的合并，要将u的子节点的信息合并到u的身上去。
那么，假设要将v的信息并到u上，则：
int merge(int u,int v) {
if (!u) return v;
if (!v) return u;
ch[u][]=merge(ch[u][],ch[v][]);
ch[u][]=merge(ch[u][],ch[v][]);
return u;
}
那么这题差不多就可以A了。
code：
%:pragma gcc optimize()
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define jug(i,x) (((1<<i)&x)>0)
#define M(a,x) memset(a,x,sizeof a)
using namespace std;
,Nod=;
int n,tot,Q,a[N],lnk[N],nxt[N],son[N];
int ro[N],ans[N];
struct que {int v,i;};
vector <que> qr[N];
struct persistent_trie {
];
;}
int newnode() {
M(ch[cnt],);
return cnt++;
}
int merge(int x,int y) {
if (!x) return y;
if (!y) return x;
ch[x][]=merge(ch[x][],ch[y][]);
ch[x][]=merge(ch[x][],ch[y][]);
return x;
}
void insert(int x,int v) {
int u=ro[x];
; i>=; i--) {
bool c=jug(i,v);
if (!ch[u][c]) ch[u][c]=newnode();
u=ch[u][c];
}
}
int query(int x,int v) {
;
; i>=; i--) {
bool c=jug(i,v);
-c]) ret|=(<<i),u=ch[u][-c];
else u=ch[u][c];
}
return ret;
}
}pt;
inline int read() {
; char ch=getchar();
') ch=getchar();
+ch-',ch=getchar();
return x;
}
void add(int x,int y) {
nxt[++tot]=lnk[x],son[tot]=y,lnk[x]=tot;
}
void DFS(int x) {
ro[x]=pt.newnode();
pt.insert(x,a[x]);
for (int j=lnk[x]; j; j=nxt[j])
DFS(son[j]),ro[x]=pt.merge(ro[x],ro[son[j]]);
,si=qr[x].size(); i<si; i++)
ans[qr[x][i].i]=pt.query(x,qr[x][i].v);
}
int main() {
while (scanf("%d%d",&n,&Q)!=EOF) {
tot=,M(lnk,),M(nxt,),M(ans,),pt.init();
; i<=n; i++) a[i]=read();
; i<n; i++) {
);
}
; i<=n; i++) qr[i].clear();
; i<=Q; i++) {
int x=read(); que now;
now.i=i,now.v=read(),qr[x].push_back(now);
}
DFS();
; i<=Q; i++) printf("%d\n",ans[i]);
}
;
}