本文共 3038 字，大约阅读时间需要 10 分钟。
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:
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.
For each operation,print its result.
Input:
8 5105 2 9 3 8 5 7 71 2 1 31 43 53 63 74 8 2 5 1 2 5 2 2 5 3 2 5 4 7 8 2
Output:2 8 9 105 7 【分析】在树上建立主席树，然后LCA。
#include #include #include #include #include #include #include #include #include #include #include #include #include #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 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] =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
转载于:https://www.cnblogs.com/jianrenfang/p/6374569.html