洛谷 P2633/bzoj 2588/spoj 10628 Count on a tree 题解【可持久化】【主席树】【树上前缀和】【倍增】【LCA】

点击量：164

    看上去是个类似树剖的东西，不过是用树上前缀和做的。（树上两点间路径操作不要只想着树剖啊，要想到树上差分/前缀和）

目录

题目描述

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

 

输入输出格式

输入格式：

第一行两个整数N,M。

 

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

 

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

 

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

 

输出格式：

M行，表示每个询问的答案。

 

输入输出样例

输入样例#1：

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

输出样例#1：

2
8
9
105
7

说明

N,M<=100000

题解：

    这个题树剖的话反而不好做，因为状态不连续，没有关联。而对于每一组询问，维护树上前缀和是比较靠谱的。

    因为这个题没有修改，所以联想到静态区间第K大，是主席树干的事。而树上如果要维护有关联的路径，就要用到前缀和。而线段树具有加加减减的特性，因此是可以维护这种前缀和的。

    因为树上前缀和用到了容斥原理，所以对于树上两点u,v的路径的信息，查询到的结果是

$ ans_u+ans_v-ans_{lca(u,v)}-ans_{fa[lca(u,v)]}$

(为了防止lca被计算两遍)

    而主席树的查询本来就是$ [l,r]\rightarrow [1,r]-[1,l)$，因此上面的式子模仿这个就可以查询u到v路径上的信息，而静态区间第K大也是一样的（luogu模板题的形式）。

    莫名感觉写主席树肥肠爽！

    注意SPOJ不强制在线。（记得离散化）

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid (l+r>>1)
#define Mid (this->l+this->r>>1)
struct node
{
    int l,r,v;
    node *ls,*rs;
    node(int l,int r)
    {
        this->l=l;
        this->r=r;
        v=0;
        ls=NULL;
        rs=NULL;
    }
    node()
    {
        ls=NULL;
        rs=NULL;
        v=0;
    }
    void build(int l,int r)//空树
    {
        this->l=l;
        this->r=r;
        if(l==r)
            return;
        ls=new node();
        ls->build(l,mid);
        rs=new node();
        rs->build(mid+1,r);
    }
    void build(node *pre,int p)//依赖前面的树
    {
        this->l=pre->l;
        this->r=pre->r;
        this->v=pre->v;
        if(l==r)
        {
            v++;
            return;
        }
        if(p<=Mid)
        {
            rs=pre->rs;
            ls=new node();
            ls->build(pre->ls,p);
        }
        else
        {
            ls=pre->ls;
            rs=new node();
            rs->build(pre->rs,p);
        }
        v=ls->v+rs->v;
    }
}*root[101000];//1e5个线段树
struct Pair
{
    int i,n,ori;
    friend bool operator <(Pair a,Pair b)
    {
        return a.ori<b.ori;
    }
}a[100100];
bool cmp(Pair a,Pair b)
{
    return a.i<b.i;
}
struct edge
{
    int n,nxt;
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
    }
    edge()
    {
        nxt=-1;
    }
}e[200100];
int head[101000],ecnt=-1;
void add(int from,int to)
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
int f[100100][20];
int d[100100];
void dfs(int x)
{
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=f[x][0])
        {
            root[e[i].n]=new node();
            root[e[i].n]->build(root[x],a[e[i].n].n);
            f[e[i].n][0]=x;
            d[e[i].n]=d[x]+1;
            dfs(e[i].n);
        }
    return;
}
int n;
void init()//倍增LCA预处理
{
    for(int i=1;i<=18;i++)
        for(int j=1;j<=n;j++)
            f[j][i]=f[f[j][i-1]][i-1];
}
int lca(int x,int y)
{
    if(d[x]<d[y])
    {
        int t=x;
        x=y;
        y=t;
    }
    for(int i=18;i>=0;i--)
        if(d[f[x][i]]>=d[y])
            x=f[x][i];
    if(x==y)
        return x;
    for(int i=18;i>=0;i--)
        if(f[x][i]!=f[y][i])
        {
            x=f[x][i];
            y=f[y][i];
        }
    return f[x][0]==0?1:f[x][0];
}
int Hash[101000];
int ask(node *rt1,node *rt2,node *rt3,node *rt4,int k)//主席树查询
{
    if(rt1->l==rt1->r)
        return rt1->l;
    int tmp=rt1->ls->v+rt2->ls->v-rt3->ls->v-rt4->ls->v;
    if(tmp>=k)
        return ask(rt1->ls,rt2->ls,rt3->ls,rt4->ls,k);
    return ask(rt1->rs,rt2->rs,rt3->rs,rt4->rs,k-tmp);
}
int query(int x,int y,int k)
{
    int a1=lca(x,y);
    int a2=f[a1][0];
    return ask(root[x],root[y],root[a1],root[a2],k);
}
int main()
{
    memset(head,-1,sizeof(head));
    int q,u,v,k;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].ori);
        a[i].i=i;
    }
    std::sort(a+1,a+1+n);//离散化
    for(int i=1;i<=n;i++)
    {
        a[i].n=i;
        Hash[i]=a[i].ori;
    }
    std::sort(a+1,a+1+n,cmp);
    root[0]=new node();
    root[1]=new node();
    root[0]->build(1,n);//建立空树
    root[1]->build(root[0],a[1].n);
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    f[1][0]=0;//1的父亲设成0，表示空树
    d[1]=1;
    dfs(1);
    init();
    int lastans=0;//强制在线
    while(q--)
    {
        scanf("%d%d%d",&u,&v,&k);
        u^=lastans;
        lastans=Hash[query(u,v,k)];
        printf("%d\n",lastans);
    }
    return 0;
}