글 제목 SPOJ - COT - Count on a tree (LCA + 주석 트 리)

제목 링크
제목: 트 리 의 경로 u - > v 의 k 작은 노드 구하 기
분석: 일반적인 K 가 크 고 현재 의 이 선분 나 무 는 앞의 선분 나 무 를 바탕 으로 세 워 진 것 이 며 나무의 K 가 크 면 현재 의 선분 나 무 는 아버지 노드 의 선분 나 무 를 세 울 수 있 습 니 다.그래서 우 리 는 u - > v 의 k 대 는 rt [u] + rt [v] - rt [lca (u, v)] - rt [fa [lca (u, v)] 의 k 대 를 조회 합 니 다.
코드:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;

const int mod=1e9+7;
const int maxn=2e5+10;
int n,q;
int a[maxn],ha[maxn]; 

int sum[maxn*40],ls[maxn*40],rs[maxn*40],rt[maxn*40];
int tot;
int sz;
//    
void build (int &num,int l,int r){
    num=++tot;
    sum[num]=0;
    if (r==l)return;
    int mid=(l+r)/2;
    build (ls[num],l,mid);
    build (rs[num],mid+1,r);
}

void update(int &num,int l,int r,int last,int pos){
    num=++tot;
    ls[num]=ls[last];
    rs[num]=rs[last];
    sum[num]=sum[last]+1;
    if (l==r)return ;
    int mid=(l+r)/2;
    if (pos<=mid)update(ls[num],l,mid,ls[last],pos);
    else update(rs[num],mid+1,r,rs[last],pos);
}

int query(int u,int v,int lca,int lcafa,int l,int r,int k){
    if (l==r)return l;
    int mid=(l+r)/2;
    int cnt=sum[ls[u]]+sum[ls[v]]-sum[ls[lca]]-sum[ls[lcafa]];
    if (cnt>=k)return query(ls[u],ls[v],ls[lca],ls[lcafa],l,mid,k);
    else return query(rs[u],rs[v],rs[lca],rs[lcafa],mid+1,r,k-cnt);
}

//LCA
int dis[maxn];//dis[i]    i       
int dp[maxn*2][20];
int first[maxn];//first[i]  i             
int dep[maxn*2];//   
int point[maxn*2];//point[i]     i       
int vis[maxn];//            
int cnt;//         
int fa[maxn];
vector<int>G[maxn];

void dfs(int u,int father,int idx){
    vis[u]=true;
    point[++cnt]=u;//point       
    first[u]=cnt;//first  u            
    dep[cnt]=idx;//  
    fa[u]=father;
    update(rt[u],1,sz,rt[father],a[u]);
    for (int i=0;iint v=G[u][i];
        if (!vis[v]){
            dfs(v,u,idx+1);
            point[++cnt]=u;
            dep[cnt]=idx;
        }
    }
}
void RMQ_init(int n){
    for (int i=1;i<=n;i++)dp[i][0]=i;
    for (int k=1;(1<for (int i=1;i+(1<1<=n;i++){
            int a=dp[i][k-1];
            int b=dp[i+(1<1))][k-1];
            if (dep[a]>dep[b])dp[i][k]=b;
            else dp[i][k]=a;
        }
    }
} 

int RMQ(int l,int r){
    int k=0;
    while ((1<1))<=r-l+1)k++;
    int a=dp[l][k];
    int b=dp[r-(1<1][k];//      
    return dep[a]>dep[b]?b:a;
}

int LCA(int u,int v){// LCA 
    int x=first[u],y=first[v];
    if (x>y)swap(x,y);
    int ans=RMQ(x,y);
    return point[ans];
}

int main()
{
    while (scanf ("%d%d",&n,&q)!=EOF){
        for (int i=0;i<=n;i++)G[i].clear();
        memset (vis,0,sizeof (vis));
        for (int i=1;i<=n;i++){
            scanf ("%d",&a[i]);
            ha[i]=a[i];
        }
        int u,v,k;
        for (int i=0;i1;i++){
            scanf ("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        sort(ha+1,ha+1+n);
        sz=unique(ha+1,ha+1+n)-(ha+1);
        for (int i=1;i<=n;i++){
            a[i]=lower_bound(ha+1,ha+1+sz,a[i])-ha;
        }
        tot=cnt=0;
        build(rt[0],1,sz);
        dfs(1,0,1);
        RMQ_init(2*n-1);
        while (q--){
            scanf ("%d%d%d",&u,&v,&k);
            int lca=LCA(u,v);
            int ans=query(rt[u],rt[v],rt[lca],rt[fa[lca]],1,sz,k);
            printf ("%d
",ha[ans]);
        }
    }
    return 0;
}
/*
8 6
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
2 5 2
2 5 3
2 5 4
7 8 2
5 7 1
*/