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 a[i](0<=a[i]<2^{16}) 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.

 

Sample Input

 

Sample Output

 

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <sstream>

#include <cstring>

#include <bitset>

#include <string>

#include <deque>

#include <stack>

#include <cmath>

#include <queue>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=1e5+7;

struct Trie

{

    int nxt[2];

    int cnt;

};

struct edge

{

    int to,nxt;

};

struct Query

{

    int to,nxt,id,lca;

};

struct ask

{

    int u,v,lca,val;

};

ask q[N];

Trie L[N*18];int cnt;

Query Q[N<<1];int qtot,qhead[N];

edge E[N<<1];int tot,head[N];

int ances[N],pre[N],Father[N];

bitset<N>vis;

int arr[N],root[N];

void init()

{

    CLR(L,0);cnt=0;

    CLR(head,-1);tot=0;

    CLR(qhead,-1);qtot=0;

    CLR(ances,0);

    for (int i=0; i<N; ++i)

        pre[i]=i;

    CLR(Father,0);

    vis.reset();

    CLR(root,0);

}

inline void add(const int &s,const int &t)

{

    E[tot].to=t;

    E[tot].nxt=head[s];

    head[s]=tot++;

}

inline void addQ(const int &s,const int &t,const int &id)

{

    Q[qtot].to=t;

    Q[qtot].id=id;

    Q[qtot].lca=1;

    Q[qtot].nxt=qhead[s];

    qhead[s]=qtot++;

}

void update(int &cur,const int &ori,const int &step,const int &n)

{

    cur=++cnt;

    L[cur]=L[ori];

    ++L[cur].cnt;

    if(step<0)

        return;

    int t=(n>>step)&1;

    update(L[cur].nxt[t],L[ori].nxt[t],step-1,n);

}

int Find(const int &n)

{

    return n==pre[n]?n:pre[n]=Find(pre[n]);

}

void Tarjan(const int &u,const int &Fa)

{

    vis[u]=1;

    ances[u]=u;

    Father[u]=Fa;

    update(root[u],root[Fa],16,arr[u]);

    for (int i=head[u]; ~i; i=E[i].nxt)

    {

        int v=E[i].to;

        if(!vis[v])

        {

            Tarjan(v,u);

            pre[v]=u;

            ances[Find(u)]=u;

        }

    }

    for (int i=qhead[u]; ~i; i=Q[i].nxt)

    {

        int v=Q[i].to;

        if(vis[v])

            q[Q[i].id].lca=ances[Find(v)];

    }

}

int query(const int &U,const int &V,const int &LCA,const int &F_LCA,const int &step,const int &n)

{

    if(step<0)

        return 0;

    int t=(n>>step)&1;

    int c=L[L[U].nxt[t^1]].cnt+L[L[V].nxt[t^1]].cnt-L[L[LCA].nxt[t^1]].cnt-L[L[F_LCA].nxt[t^1]].cnt;

    if(c>0)

        return (1<<step)+query(L[U].nxt[t^1],L[V].nxt[t^1],L[LCA].nxt[t^1],L[F_LCA].nxt[t^1],step-1,n);

    else

        return query(L[U].nxt[t],L[V].nxt[t],L[LCA].nxt[t],L[F_LCA].nxt[t],step-1,n);

}

int main(void)

{

    int n,m,a,b,i;

    while (~scanf("%d%d",&n,&m))

    {

        init();

        for (i=1; i<=n; ++i)

            scanf("%d",&arr[i]);

        for (i=0; i<n-1; ++i)

        {

            scanf("%d%d",&a,&b);

            add(a, b);

            add(b, a);

        }

        for (i=0; i<m; ++i)

        {

            scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].val);

            addQ(q[i].u, q[i].v, i);

            addQ(q[i].v, q[i].u, i);

        }

        Tarjan(1,0);

        for (i=0; i<m; ++i)

            printf("%d\n",query(root[q[i].u],root[q[i].v],root[q[i].lca],root[Father[q[i].lca]],16,q[i].val));

    }

    return 0;

}

int update(int ori,int n)

{

    bitset<17> s=n;

    int cur=++cnt;

    int ret=cur;

    L[cur]=L[ori];

    for (int i=16; i>=0; --i)

    {

        int v=s[i];

        L[++cnt]=L[L[cur].nxt[v]];

        ++L[cnt].cnt;

        L[cur].nxt[v]=cnt;

        cur=cnt;

    }

    return ret;

}

void Tarjan(const int &u,const int &Fa)

{

    /*vis[u]=1;

    ances[u]=u;

    Father[u]=Fa;*/

    root[u]=update(root[Fa],arr[u]);

    /*for (int i=head[u]; ~i; i=E[i].nxt)

    {

        int v=E[i].to;

        if(!vis[v])

        {

            Tarjan(v,u);

            pre[v]=u;

            ances[Find(u)]=u;

        }

    }

    for (int i=qhead[u]; ~i; i=Q[i].nxt)

    {

        int v=Q[i].to;

        if(vis[v])

            q[Q[i].id].lca=ances[Find(v)];

    }*/

}

int query(int u,int v,int lca,int flca,int n)

{

    int r=0;

    bitset<17> s=n;

    for (int i=16; i>=0; --i)

    {

        int indx=s[i];

        int c=L[L[u].nxt[indx^1]].cnt+L[L[v].nxt[indx^1]].cnt-L[L[lca].nxt[indx^1]].cnt-L[L[flca].nxt[indx^1]].cnt;

        if(c>0)

        {

            r+=1<<i;

            u=L[u].nxt[indx^1];

            v=L[v].nxt[indx^1];

            lca=L[lca].nxt[indx^1];

            flca=L[flca].nxt[indx^1];

        }

        else

        {

            u=L[u].nxt[indx];

            v=L[v].nxt[indx];

            lca=L[lca].nxt[indx];

            flca=L[flca].nxt[indx];

        }

    }

    return r;

}