SPOJ 10628 COT

COT - Count on a tree

#tree

You are given a tree with N nodes.The tree nodes are numbered from 1 to N.Each node has an integer weight.

We will ask you to perform the following operation:

u v k : ask for the kth minimum weight on the path from node u to node v

Input

In the first line there are two integers N and M.(N,M<=100000)

In the second line there are N integers.The ith integer denotes the weight of the ith node.

In the next N-1 lines,each line contains two integers u v,which describes an edge (u,v).

In the next M lines,each line contains three integers u v k,which means an operation asking for the kth minimum weight on the path from node u to node v.

Output

For each operation,print its result.

Example

Input:

8 5

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
2 5 2
2 5 3
2 5 4
7 8 2

Output:
2
8
9
105
7 
【分析】在树上建立主席树，然后LCA。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define lson(x) ((x<<1))
#define rson(x) ((x<<1)+1)
using namespace std;
typedef long long ll;
const int N=1e5+50;
const int M=N*N+10;
struct seg {
    int lson,rson;
    int cnt;
};
struct man{
    int to,next;
}edg[2*N];
seg T[N*20];
int root[N],tot,cnt,n,m;
vector<int>pos;
int arr[N];
int fa[2*N][20],head[N*2],dis[N*2],dep[N*2];
void init() {
    pos.clear();
    met(root,0);met(head,-1);
    tot=cnt=0;
    T[0].cnt=T[0].lson=T[0].rson=0;
}
void add(int u,int v){
    edg[cnt].to=v;edg[cnt].next=head[u];head[u]=cnt++;
}
void update(int &cur,int ori,int l,int r,int pos,int flag) {
    cur=++tot;
    T[cur]=T[ori];
    T[cur].cnt+=flag;
    if(l==r)
        return ;
    int mid=(l+r)/2;
    if(pos<=mid)
        update(T[cur].lson,T[ori].lson,l,mid,pos,flag);
    else
        update(T[cur].rson,T[ori].rson,mid+1,r,pos,flag);
}
int query(int ru,int rv,int lca,int rlca,int l,int r,int k) {
    if(l==r)return l;
    int mid=(l+r)/2;
    int sum=T[T[ru].lson].cnt+T[T[rv].lson].cnt-T[T[lca].lson].cnt-T[T[rlca].lson].cnt;
    if(sum>=k)return query(T[ru].lson,T[rv].lson,T[lca].lson,T[rlca].lson,l,mid,k);
    else query(T[ru].rson,T[rv].rson,T[lca].rson,T[rlca].rson,mid+1,r,k-sum);
}
void dfs(int u,int f){
    fa[u][0]=f;
    for(int i=1;i<20;i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    update(root[u],root[f],1,n,arr[u],1);
    for(int i=head[u];i!=-1;i=edg[i].next){
        int v=edg[i].to;
        if(v!=f){
            dep[v]=dep[u]+1;
            dfs(v,u);
        }
    }
}
int LCA(int u,int v){
    int U=u,V=v;
    if(dep[u]<dep[v])swap(u,v);
    for(int i=19;i>=0;i--){
        if(dep[fa[u][i]]>=dep[v]){
            u=fa[u][i];
        }
    }
    if(u==v)return (u);
    for(int i=19;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];v=fa[v][i];
        }
    }
    return (fa[u][0]);
}
int main(void) {
    int i,l,r,k,u,v;
    scanf("%d%d",&n,&m);
    init();
    for (i=1; i<=n; ++i) {
        scanf("%d",&arr[i]);
        pos.push_back(arr[i]);
    }
    sort(pos.begin(),pos.end());
    pos.erase(unique(pos.begin(),pos.end()),pos.end());
    int temp_rt=0;
    for (i=1; i<=n; ++i) {
        arr[i]=lower_bound(pos.begin(),pos.end(),arr[i])-pos.begin()+1;
    }
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dep[1]=1;
    dfs(1,0);
    for (i=0; i<m; ++i) {
        scanf("%d%d%d",&u,&v,&k);
        int lca=LCA(u,v);
        int f=fa[lca][0];
       printf("%d
",pos[query(root[u],root[v],root[lca],root[f],1,n,k)-1]);
    }
    return 0;
}