[TS-A1505] [清橙2013中国国家集训队第二次作业] 树 [可持久化线段树，求树上路径第k大]

按Dfs序逐个插入点，建立可持久化线段树，每次查询即可，具体详见代码。

不知道为什么，代码慢的要死，，

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ctime>

#include <vector>

using namespace std;

template<const int _n,const int _m>

struct Edge

{

    struct Edge_base { int    to,next; }e[_m];

    int    cnt,p[_n];

    Edge() { clear(); }

    void    insert(const int x,const int y)

    { e[++cnt].to=y; e[cnt].next=p[x]; p[x]=cnt; return ; }

    int    start(const int x) { return p[x]; }

    void    clear() { cnt=,memset(p,,sizeof(p)); }

    Edge_base&    operator[](const int x) { return e[x]; }

};

Edge<,>    e;

vector<int>    vec;

int    n,q,tot,cnt;

int    a[],root[],Left[],Right[];

int    val[],f[][],depth[],lg2[];

void    Init()

{

    for(int j=;(<<j)<=n;++j)

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

            f[i][j]=f[f[i][j-]][j-];

    for(int i=;i<=n;++i)lg2[i]=lg2[i>>]+;

    return ;

}

int    Lca(int A,int B)

{

    int    i,j;

    if(depth[A]<depth[B])swap(A,B);

    j=lg2[depth[A]];

    for(i=j;i>=;--i)

    {

        if(depth[A]-(<<i)>=depth[B])A=f[A][i];

    }

    if(A==B)return A;

    for(i=j;i>=;--i)

    {

        if(f[A][i] && f[A][i]!=f[B][i])

            A=f[A][i],B=f[B][i];

    }

    return f[A][];

}

void    Insert(const int l,const int r,const int root_l,int& root_r,const int d)

{

    val[root_r=++tot]=val[root_l]+;

    if(l==r)return ;

    int mid=l+((r-l)>>);

    if(d<=mid)

    {

        Right[root_r]=Right[root_l];

        Insert(l,mid,Left[root_l],Left[root_r],d);

    }

    else

    {

        Left[root_r]=Left[root_l];

        Insert(mid+,r,Right[root_l],Right[root_r],d);

    }

    return ;

}

void    Dfs(const int S,const int fa)

{

    depth[S]=depth[fa]+;

    f[S][]=fa;

    a[S]=lower_bound(vec.begin(),vec.end(),a[S])-vec.begin()+;

    Insert(,vec.size(),root[fa],root[S],a[S]);

    for(int i=e.start(S);i;i=e[i].next)

    {

        if(e[i].to==fa)continue;

        Dfs(e[i].to,S);

    }

}

int    kth(int l,int r,int r1,int r2,int r3,int r4,int d)

{

    while(true)

    {

        if(l==r)return l;

        int    mid=l+((r-l)>>),temp;

        temp=val[Left[r1]]+val[Left[r2]]-val[Left[r3]]-val[Left[r4]];

        if(temp>=d)r=mid,r1=Left[r1],r2=Left[r2],r3=Left[r3],r4=Left[r4];

        else    l=mid+,r1=Right[r1],r2=Right[r2],r3=Right[r3],r4=Right[r4],d=d-temp;

    }

    return ;

}

int main()

{

    //freopen("in","r",stdin);

    int    i,x,y,op;

    vec.resize();

    scanf("%d%d",&n,&q);

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

        scanf("%d",&a[i]),vec.push_back(a[i]);

    sort(vec.begin(),vec.end());

    vec.erase(unique(vec.begin(),vec.end()),vec.end());

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

    {

        scanf("%d%d",&x,&y);

        e.insert(x,y);

        e.insert(y,x);

    }

    Dfs(,);

    Init();

    for(i=;i<=q;++i)

    {

        scanf("%d%d%d",&op,&x,&y);

        int    temp=Lca(x,y),temp1;

        if(op==)

            temp1=kth(,vec.size(),

                    root[x],root[y],

                    root[temp],root[f[temp][]],);

        else if(op==)

            temp1=kth(,vec.size(),

                    root[x],root[y],

                    root[temp],root[f[temp][]],

                    depth[x]+depth[y]-(depth[temp]<<)+);

        else    temp1=kth(,vec.size(),

                root[x],root[y],

                root[temp],root[f[temp][]],

                ((depth[x]+depth[y]-(depth[temp]<<)+)>>)+);

        printf("%d\n",vec[temp1-]);

    }

    return ;

}