AC日记——Count on a tree bzoj 2588

Description

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

Input

第一行两个整数N,M。

第二行有N个整数，其中第i个整数表示点i的权值。

后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。

最后M行每行两个整数(u,v,k)，表示一组询问。

Output

M行，表示每个询问的答案。最后一个询问不输出换行符

Sample Input

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
0 5 2
10 5 3
11 5 4
110 8 2

Sample Output

2
8
9
105
7

HINT

HINT：

N,M<=100000

暴力自重。。。

思路：

　　主席树；

　　树上一段路径中主席树的状态可以用root[from]+root[to]-root[lca]-root[f[lca]]来表示

　　但是，这个题和spoj上不太一样

　　要用到long long

　　而且每次的from都是一个二进制数，需要xor上一次查询的答案；

来，上代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define LL long long

#define maxn 100001

using namespace std;

struct TreeNodeType {

    LL dis,lc,rc;

};

struct TreeNodeType tree[maxn*];

struct EdgeType {

    LL to,next;

};

struct EdgeType edge[maxn<<];

LL if_z,n,m,hash[maxn],hash_[maxn],cnt,head[maxn];

LL size_,tot,root[maxn],deep[maxn],f[maxn],size[maxn];

LL belong[maxn];

char Cget;

inline void read_int(LL &now)

{

    now=,if_z=,Cget=getchar();

    while(Cget>''||Cget<'')

    {

        if(Cget=='-') if_z=-;

        Cget=getchar();

    }

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

    now*=if_z;

}

inline void edge_add(LL from,LL to)

{

    cnt++;

    edge[cnt].to=to;

    edge[cnt].next=head[from];

    head[from]=cnt;

}

void tree_build(LL now,LL l,LL r)

{

    tree[now].dis=;

    if(l==r) return ;

    LL mid=(l+r)>>;

    tree[now].lc=++tot;

    tree_build(tot,l,mid);

    tree[now].rc=++tot;

    tree_build(tot,mid+,r);

}

void tree_add(LL pre,LL now,LL to,LL l,LL r)

{

    tree[now].dis=tree[pre].dis+;

    if(l==r) return ;

    LL mid=(l+r)>>;

    if(to>mid)

    {

        tree[now].lc=tree[pre].lc;

        tree[now].rc=++tot;

        tree_add(tree[pre].rc,tree[now].rc,to,mid+,r);

    }

    else

    {

        tree[now].rc=tree[pre].rc;

        tree[now].lc=++tot;

        tree_add(tree[pre].lc,tree[now].lc,to,l,mid);

    }

}

void search(LL now,LL pre)

{

    LL pos=cnt++;

    f[now]=pre;

    deep[now]=deep[pre]+;

    hash_[now]=lower_bound(hash+,hash+size_+,hash_[now])-hash;

    root[now]=++tot;

    tree_add(root[pre],root[now],hash_[now],,size_);

    for(LL i=head[now];i;i=edge[i].next)

    {

        if(edge[i].to==pre) continue;

        search(edge[i].to,now);

    }

    size[now]=cnt-pos;

}

void search_(LL now,LL chain)

{

    LL pos=;

    belong[now]=chain;

    for(LL i=head[now];i;i=edge[i].next)

    {

        if(edge[i].to==f[now]) continue;

        if(size[edge[i].to]>size[pos]) pos=edge[i].to;

    }

    if(pos==) return ;

    search_(pos,chain);

    for(LL i=head[now];i;i=edge[i].next)

    {

        if(pos==edge[i].to||edge[i].to==f[now]) continue;

        search_(edge[i].to,edge[i].to);

    }

}

inline LL tree_lca(LL x,LL y)

{

    while(belong[x]!=belong[y])

    {

        if(deep[belong[x]]<deep[belong[y]]) swap(x,y);

        x=f[belong[x]];

    }

    if(deep[x]<deep[y]) return x;

    else return y;

}

inline LL tree_query(LL x,LL y,LL lca,LL flca,LL l,LL r,LL k)

{

    LL dis,mid;

    while(l!=r)

    {

        dis=tree[tree[x].lc].dis+tree[tree[y].lc].dis-tree[tree[lca].lc].dis-tree[tree[flca].lc].dis;

        mid=(l+r)>>;

        if(k>dis)

        {

            k-=dis;

            l=mid+;

            lca=tree[lca].rc;

            flca=tree[flca].rc;

            x=tree[x].rc,y=tree[y].rc;

        }

        else

        {

            r=mid;

            lca=tree[lca].lc;

            flca=tree[flca].lc;

            x=tree[x].lc,y=tree[y].lc;

        }

    }

    return l;

}

int main()

{

    read_int(n),read_int(m);

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

    {

        read_int(hash[i]);

        hash_[i]=hash[i];

    }

    LL from,to;

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

    {

        read_int(from),read_int(to);

        edge_add(from,to);

        edge_add(to,from);

    }

    sort(hash+,hash+n+);

    size_=unique(hash+,hash+n+)-hash-;

    root[]=++tot;

    tree_build(root[],,size_);

    cnt=,search(,);

    cnt=,search_(,);

    LL K,last=;

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

    {

        read_int(from),read_int(to),read_int(K);

        from=from^last;

        LL lca=tree_lca(from,to);

        last=hash[tree_query(root[from],root[to],root[lca],root[f[lca]],,size_,K)];

        if(i!=m) printf("%lld\n",last);

        else printf("%lld",last);

    }

    return ;

}

巴特西