Count on a tree
SPOJ - COT
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
题意：给出一颗树，求两结点第k小的数
分析：跟求区间第K大差不多，这次是维护一个树上的信息。
那么结果为 tree[a]+tree[b]-tree[lca(a,b)]-tree[father[lca(a,b)]] 因为lca结点需要保留，所以是减去父亲结点（这里的father是父亲不是祖先）
AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
const int maxn=100500;
struct zxtree
{
int num,lson,rson;
}tree[maxn<<5];
struct edge
{
int u,v;
edge(){}
edge(int uu,int vv)
{
u=uu,v=vv;
}
};
vector<edge>G;
vector<int>v[maxn];
int root[maxn];
int val[maxn],hash1[maxn];
int cnt;
int father[maxn][40],fa[maxn],maxdeep,deep[maxn];
void addedge(int a,int b)
{
G.push_back(edge(a,b));
G.push_back(edge(b,a));
int m=G.size();
v[a].push_back(m-2);
v[b].push_back(m-1);
}
void bulidzxtree(int &v,int l,int r)
{
v=++cnt;
tree[v].num=0;
if(l==r) return;
int mid=(l+r)>>1;
bulidzxtree(tree[v].lson,l,mid);
bulidzxtree(tree[v].rson,mid+1,r);
}
int Binary_search(int *p,int x,int r)
{
int l=1;
while(l<=r)
{
int mid=(l+r)>>1;
if(p[mid]<x)
l=mid+1;
else
r=mid-1;
}
return l;
}
void init(int n)
{
memset(root,0,sizeof(root));
memset(father,0,sizeof(father));
memset(fa,0,sizeof(fa));
memset(deep,0,sizeof(deep));
maxdeep=log(n*1.0)/log(2.0);
for(int i=0;i<=n;i++)
v[i].clear();
G.clear();
}
void update(int p,int &v,int l,int r,int x)
{
v=++cnt;
tree[v]=tree[p];
tree[v].num++;
if(l==r) return;
int mid=(l+r)>>1;
if(x>mid)
update(tree[p].rson,tree[v].rson,mid+1,r,x);
else
update(tree[p].lson,tree[v].lson,l,mid,x);
}
void dfs(int rt,int t)
{
update(root[fa[rt]],root[rt],1,t,val[rt]);
for(int i=1;i<=maxdeep;i++)
{
father[rt][i]=father[father[rt][i-1]][i-1];
if(father[rt][i]==0)
break;
}
for(int i=0;i<v[rt].size();i++)
{
edge &e=G[v[rt][i]];
if(father[rt][0]!=e.v)
{
father[e.v][0]=rt;
fa[e.v]=rt;
deep[e.v]=deep[rt]+1;
dfs(e.v,t);
}
}
}
int lca(int a,int b)
{
if(deep[a]>deep[b])
swap(a,b);
for(int i=maxdeep;i>=0;i--)
{
if(deep[a]<deep[b]&&deep[a]<=deep[father[b][i]])
{
b=father[b][i];
}
}
if(a==b)
return a;
for(int i=maxdeep;i>=0;i--)
{
if(father[a][i]!=father[b][i])
{
a=father[a][i];
b=father[b][i];
}
}
if(a!=b)
a=father[a][0];
return a;
}
int query(int a,int b,int lc,int ff,int l,int r,int k)
{
if(l==r) return l;
int mid=(l+r)>>1;
int ans=tree[tree[a].lson].num+tree[tree[b].lson].num-tree[tree[lc].lson].num-tree[tree[ff].lson].num;
//printf("! %d\n",ans);
if(k<=ans)
query(tree[a].lson,tree[b].lson,tree[lc].lson,tree[ff].lson,l,mid,k);
else
query(tree[a].rson,tree[b].rson,tree[lc].rson,tree[ff].rson,mid+1,r,k-ans);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2)
{
init(n);
cnt=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&val[i]);
hash1[i]=val[i];
}
sort(hash1+1,hash1+n+1);
int t=unique(hash1+1,hash1+1+n)-hash1-1;
for(int i=1;i<=n;i++)
{
val[i]=Binary_search(hash1,val[i],t);
//val[i]=lower_bound(hash+1,hash+t+1,val[i])-hash;
}
bulidzxtree(root[0],1,t);
int rt;
for(int i=0;i<n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
father[b][0]=a;
addedge(a,b);
if(!father[a][0])
rt=a;
}
deep[rt]=1;
dfs(rt,t);
for(int i=0;i<m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
int lc=lca(a,b);
int s=query(root[a],root[b],root[lc],root[fa[lc]],1,t,c);
printf("%d\n",hash1[s]);
}
}
}
