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]); } ; }