SPOJ Count on a tree 树上第k大
Description
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 uv,which describes an edge (u,v).
In the next M lines,each line contains three integers uvk,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 58 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
给定一棵树n个节点的权值，n-1条边，求路径上第k大
同样是可持久化线段树，只是这一次我们用它来维护树上的信息。我们之前已经知道，可持久化线段树实际上是维护的一个前缀和，而前缀和不一定要出现在一个线性表上。
比如说我们从一棵树的根节点进行DFS，得到根节点到各节点的距离dist[x]——这是一个根-x路径上点与根节点距离的前缀和。
利用这个前缀和，我们可以解决一些树上任意路径的问题，比如在线询问[a,b]点对的距离——答案自然是dist[a]+dist[b]-2*dist[lca(a,b)]。
同理，我们可以利用可持久化线段树来解决树上任意路径的问题。
DFS遍历整棵树，然后在每个节点上建立一棵线段树，某一棵线段树的“前一版本”是位于该节点父亲节点fa的线段树。
利用与之前类似的方法插入点权(排序离散)。那么对于询问[a,b]，答案就是root[a]+root[b]-root[lca(a,b)]-root[fa[lca(a,b)]]上的第k大。
一个地方写错，苦苦折腾了几个小时，悲剧呀。
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/4/11 18:01:43
File Name :10.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=100100;
int head[maxn],tol;
int dep[maxn],fa[maxn][20],pre[maxn],q[maxn];
int a[maxn],lisan[maxn];
int root[30*maxn],L[30*maxn],R[30*maxn],cnt,sum[30*maxn];
struct Edge{
int next,to;
}edge[4*maxn];
void addedge(int u,int v){
edge[tol].to=v;
edge[tol].next=head[u];
head[u]=tol++;
}
void bfs(int s){
int l=1,r=1;q[r++]=s;
dep[s]=0;fa[s][0]=0;pre[s]=0;
while(l!=r){
int u=q[l++];
for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;if(v==pre[u])continue;
pre[v]=u;fa[v][0]=u;dep[v]=dep[u]+1;
q[r++]=v;
}
}
}
int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=0;i<20;i++)if((dep[x]-dep[y])&(1<<i))x=fa[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void build(int l,int r,int &p){
p=++cnt;
sum[p]=0;
if(l>=r)return;
int m=(l+r)/2;
build(l,m,L[p]);
build(m+1,r,R[p]);
}
void ins(int last,int &x,int l,int r,int val){
x=++cnt;
sum[x]=sum[last]+1;
L[x]=L[last];
R[x]=R[last];
if(l==r)return;
int mid=(l+r)/2;
if(val<=mid)ins(L[last],L[x],l,mid,val);
else ins(R[last],R[x],mid+1,r,val);
}
int ask(int l,int r,int k,int nl,int nr,int l1,int l2){
if(l==r)return lisan[l];
int mid=(l+r)/2;
if(sum[L[nl]]+sum[L[nr]]-sum[L[l1]]-sum[L[l2]]<k){
k-=sum[L[nl]]+sum[L[nr]]-sum[L[l1]]-sum[L[l2]];
return ask(mid+1,r,k,R[nl],R[nr],R[l1],R[l2]);
}
return ask(l,mid,k,L[nl],L[nr],L[l1],L[l2]);
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int n,m;
while(~scanf("%d%d",&n,&m)){
memset(head,-1,sizeof(head));tol=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
lisan[i]=a[i];
}
sort(lisan+1,lisan+1+n);
int SZ=unique(lisan+1,lisan+n+1)-lisan-1;
for(int i=1;i<=n;i++)a[i]=lower_bound(lisan+1,lisan+SZ+1,a[i])-lisan;
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
bfs(1);cnt=0;
build(1,SZ,root[0]);
for(int i=1;i<=n;i++)ins(root[pre[q[i]]],root[q[i]],1,SZ,a[q[i]]);
while(m--){
int l,r,k,lca;
scanf("%d%d%d",&l,&r,&k);
lca=LCA(l,r);
printf("%d\n",ask(1,SZ,k,root[l],root[r],root[lca],root[pre[lca]]));
}
}
return 0;
}