树上第k大(主席树)

Count on a tree
题意：
给定一棵树，树上每个节点都有一个权值，问两点之间路径上第K大值
题解:
树上的第k大值，跟区间第k大有些不同，区间第k大每个值在前一个值的基础上新建一棵树，而树上第k大则是在父亲节点的基础上新建一棵树。查询的时候，答案就是root[v] + root[u] - root[lca(v, u)] - root[fa[lca(v,u)]]上的第k大(自己在纸上画一画就知道了)
关于LCA点这里

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN=100010;
struct Node
{
    int to,next;
};
Node edge[MAXN*2];
int head[MAXN],cnt;
int arr[MAXN],num[MAXN],tot,n,m;
void addEdge(int u,int v)
{
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int root[MAXN],sum[MAXN*40],lson[MAXN*40],rson[MAXN*40],cloc;
void build(int l,int r,int &rt)
{
    rt=++cloc;
    sum[rt]=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,lson[rt]);
    build(mid+1,r,rson[rt]);
}
void update(int last,int &rt,int l,int r,int pos)
{
    rt=++cloc;
    sum[rt]=sum[last]+1;lson[rt]=lson[last];rson[rt]=rson[last];
    if(l==r) return;
    int mid=(l+r)>>1;
    if(mid>=pos) update(lson[last],lson[rt],l,mid,pos);
    else update(rson[last],rson[rt],mid+1,r,pos);
}
int query(int rtu,int rtv,int lca,int falca,int l,int r,int k)
{
    if(l==r) return l;
    int tmp=sum[lson[rtu]]+sum[lson[rtv]]-sum[lson[lca]]-sum[lson[falca]];
    int mid=(l+r)>>1;
    if(tmp>=k) return query(lson[rtu],lson[rtv],lson[lca],lson[falca],l,mid,k);
    else return query(rson[rtu],rson[rtv],rson[lca],rson[falca],mid+1,r,k-tmp);
}
int sequ[MAXN*2],first[MAXN],vis[MAXN],deep[MAXN*2];
int dp[MAXN*2][20],fat[MAXN],clocks;
void DFS(int u,int fa,int dep)
{
    vis[u]=1;
    sequ[++clocks]=u;first[u]=clocks;deep[clocks]=dep;fat[u]=fa;
    update(root[fa],root[u],1,tot,arr[u]);//在父节点上建树
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            DFS(v,u,dep+1);
            sequ[++clocks]=u;
            deep[clocks]=dep;
        }
    }
}
void ST(int len)
{
    for(int i=1;i<=len;i++)
    {
        dp[i][0]=i;
    }
    for(int j=1;(1<<j)<=len;j++)
    {
        for(int i=1;i+(1<<j)-1<=len;i++)
        {
            dp[i][j]=deep[dp[i][j-1]]<deep[dp[i+(1<<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
        }
    }
}
int RMQ(int x,int y)
{
    int k=0;
    while((1<<(k+1))<=y-x+1) k++;
    return deep[dp[x][k]]<deep[dp[y-(1<<k)+1][k]]?dp[x][k]:dp[y-(1<<k)+1][k];
}
int LCA(int u,int v)
{
    int x=first[u],y=first[v];
    if(x>y) swap(x,y);
    return sequ[RMQ(x,y)];
}
int main()
{
    int u,v,rak;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",arr+i);
        num[i]=arr[i];
    }
    sort(num+1,num+1+n);
    tot=unique(num+1,num+1+n)-(num+1);
    for(int i=1;i<=n;i++) arr[i]=lower_bound(num+1,num+1+tot,arr[i])-num;
    memset(head,-1,sizeof(head));
    cnt=clocks=cloc=0;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        addEdge(u,v);
        addEdge(v,u);
    }
    build(1,tot,root[0]);
    memset(vis,0,sizeof(vis));
    DFS(1,0,1);
    ST(2*n-1);
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&u,&v,&rak);
        int lca=LCA(u,v);
        printf("%d\n",num[query(root[u],root[v],root[lca],root[fat[lca]],1,tot,rak)]);
    }
}