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.

Sample Input

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

Sample Output

3
0

题解

听说序列上的都可以放到树上做。

路径拆成两点到根和lca到根，每个点到根维护一个可持久化Trie，这样数量就是x到根+y到根-2*lca到根，这样的话lca就没选，特判下。

#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;
void add(int x,int y)
{
    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),
            add(x,y),add(y,x);
        dfs1(1),dfs2(1,1);
        for (int i=1;i<=m;i++)
            scanf("%d%d%d",&x,&y,&z),l=lca(x,y),
            printf("%d\n",max(v[l]^z,query(root[x],root[y],root[l],z,16)));
    }
}