2015
09-17

# Tree

Zero and One are good friends who always have fun with each other. This time, they decide to do something on a tree which is a kind of graph that there is only one path from node to node. First, Zero will give One an tree and every node in this tree has a value. Then, Zero will ask One a series of queries. Each query contains three parameters: x, y, z which mean that he want to know the maximum value produced by z xor each value on the path from node x to node y (include node x, node y). Unfortunately, One has no idea in this question. So he need you to solve it.

There are several test cases and the cases end with EOF. For each case:

The first line contains two integers n(1<=n<=10^5) and m(1<=m<=10^5), which are the amount of tree’s nodes and queries, respectively.

The second line contains n integers a[1..n] and a[i](0<=a[i]<2^{16}) is the value on the ith node.

The next n�C1 lines contains two integers u v, which means there is an connection between u and v.

The next m lines contains three integers x y z, which are the parameters of Zero’s query.

There are several test cases and the cases end with EOF. For each case:

The first line contains two integers n(1<=n<=10^5) and m(1<=m<=10^5), which are the amount of tree’s nodes and queries, respectively.

The second line contains n integers a[1..n] and a[i](0<=a[i]<2^{16}) is the value on the ith node.

The next n�C1 lines contains two integers u v, which means there is an connection between u and v.

The next m lines contains three integers x y z, which are the parameters of Zero’s query.

3 2
1 2 2
1 2
2 3
1 3 1
2 3 2

3
0

//可持久化trie树，题目已知一棵树，每个点有点权，询问一对点路径上点权与给定值异或的最大值
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100100
using namespace std;

struct Edge{
int v,next;
}edge[N*2];

edge[cnt].v=v;
edge[cnt].v=u;
}

struct Trie{
int go[2],cnt;
}trie[N*17];
int root[N],tot;

int insert(int id,int num){
int p=++tot,tem=p;
trie[p]=trie[id];
for(int i=15;i>=0;i--){
int tmp=(num>>i)&1;
trie[++tot]=trie[trie[p].go[tmp]];
trie[tot].cnt++;
trie[p].go[tmp]=tot;
p=tot;
}
return tem;
}

void dfs(int u,int father){
root[u]=insert(root[father],val[u]);
int v=edge[i].v;
if(v==father)continue;
dfs(v,u);
}
}

struct Query{
int v,id,w,next;
}query[N*2];

bool flag[N];

void addedge2(int u,int v,int w,int id){
query[cnt2].v=v;
query[cnt2].w=w;
query[cnt2].id=id;
query[cnt2].v=u;
query[cnt2].w=w;
query[cnt2].id=id;
}

int find(int u){
if(u==f[u]) return u;
return f[u]=find(f[u]);
}

void tarjan(int u,int father){
int v=edge[i].v;
if(v==father) continue;
tarjan(v,u);
f[v]=u;
}
flag[u]=1;
int v=query[i].v;
if(flag[v]){
lca[query[i].id]=find(v);
}
}
}

int findans(int u,int v,int LCA,int num){
int p1=root[u],p2=root[v],p3=root[LCA],ans_tmp=0;
for(int i=15;i>=0;i--){
int tmp=(num>>i)&1;
int sum=trie[trie[p1].go[!tmp]].cnt+trie[trie[p2].go[!tmp]].cnt-2*trie[trie[p3].go[!tmp]].cnt;
if(sum>0){
p1=trie[p1].go[!tmp];
p2=trie[p2].go[!tmp];
p3=trie[p3].go[!tmp];
ans_tmp+=1<<i;
}
else{
p1=trie[p1].go[tmp];
p2=trie[p2].go[tmp];
p3=trie[p3].go[tmp];
}
}
return max(ans_tmp,num^val[LCA]);
}

void solve(){
for(int i=1;i<=n;i++)
int id=query[j].id;
if(ans[id]!=-1)continue;
ans[id]=findans(i,query[j].v,lca[id],query[j].w);
}
for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}

void init(){
memset(ans,-1,sizeof(ans));
cnt=cnt2=0;
}

int main(){
int u,v,w;
while(scanf("%d %d",&n,&m)!=EOF){
init();
for(int i=1;i<=n;i++) scanf("%d",&val[i]);
for(int i=1;i<n;i++){
scanf("%d %d",&u,&v);
}
root[0]=0;
trie[0].go[0]=trie[0].go[1]=0;
trie[0].cnt=0;
tot=0;
dfs(1,0);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&u,&v,&w);