# hdu 4757 Tree

### Problem Description

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.

### Input

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 ai is the value on the ith node.

The next n–1 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.

### Output

For each query, output the answer.

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

3
0

### 题解

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;
int fa[N],son[N],siz[N],top[N],v[N],deep[N];
int cnt=0,x,y,z,l;
struct node
{
int to,next;
}e[N*2];
int tot,st[N];
int n,m;
{
e[++tot].to=y;
e[tot].next=st[x];
st[x]=tot;
}
int val[N*20],ch[N*20][2],root[N],sz;
void insert(int &now,int x,int dep)
{
val[++sz]=val[now]+1,ch[sz][0]=ch[now][0],ch[sz][1]=ch[now][1],now=sz;
if (dep==-1) return;
insert(ch[now][(x>>dep)&1],x,dep-1);
}
void dfs1(int now)
{
root[now]=root[fa[now]];
insert(root[now],v[now],16);
siz[now]=1,son[now]=now;
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=fa[now])
{
deep[e[i].to]=deep[now]+1,fa[e[i].to]=now;
dfs1(e[i].to),siz[now]+=siz[e[i].to];
if (son[now]==now||siz[e[i].to]>siz[son[now]])
son[now]=e[i].to;
}
}
void dfs2(int now,int tops)
{
top[now]=tops;
if (son[now]!=now)
dfs2(son[now],tops);
for (int i=st[now];i;i=e[i].next)
if (e[i].to!=fa[now] && e[i].to!=son[now])
dfs2(e[i].to,e[i].to);
}
int lca(int x,int y)
{
for (;top[x]!=top[y];deep[top[x]]<deep[top[y]]?y=fa[top[y]]:x=fa[top[x]]);
return deep[x]>deep[y]?y:x;
}
int query(int a,int b,int c,int x,int dep)
{
if (dep==-1) return 0;
int k=(x>>dep)&1;
if (val[ch[a][k^1]]+val[ch[b][k^1]]-val[ch[c][k^1]]*2>0)
return (query(ch[a][k^1],ch[b][k^1],ch[c][k^1],x,dep-1)|(1<<dep));
else
return query(ch[a][k],ch[b][k],ch[c][k],x,dep-1);
}
void init()
{
memset(st,0,sizeof st);
memset(ch,0,sizeof ch);
memset(val,0,sizeof val);
sz=tot=0;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
init();
for (int i=1;i<=n;i++)
scanf("%d",&v[i]);
for (int i=1;i<n;i++)
scanf("%d%d",&x,&y),