SPOJ 10628 -- 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 

  ： u v     K  

  ：       K   ，     K                 ，                    。

 
  
#include 
#include 
#include 
#include 
using namespace std;
#define maxn 208000
#define maxm 2500000
int T[maxn],first[100080],nxt[maxn],vv[maxn],dfn[maxn],dep[maxn],key[maxn],X[maxn];
int c[maxm],lson[maxm],rson[maxm];
int tot,e,n,m,fuck,cnt;
int fa[maxn][20];//fa[i][j]  i 2^j    。
void scanf_(int & num)
{
	char in;
	while((in=getchar())>'9'||in='0'&&in<='9') 
		 num*=10,num+=in-'0'; 
}
void addedge(int u,int v)
{
	vv[e] = v;	nxt[e] = first[u];	first[u] = e++;
	vv[e] = u;	nxt[e] = first[v];	first[v] = e++;
}

int build(int l,int r)
{
	int root = tot++;
	c[root] = 0;
	if(l != r)
	{
		int mid = (l+r) >> 1;
		lson[root] = build(l,mid);
		rson[root] = build(mid+1,r);
	}
	return root;
}

int Update(int root,int pos,int val)
{
	int newnode = tot++,tmp = newnode;
	c[newnode] = c[root] + val;
	int l = 1,r = fuck;
	while(l < r)
	{
		int mid = (l+r) >> 1;
		if(pos <= mid)
		{
			r = mid;
			lson[newnode] = tot++;		rson[newnode] = rson[root];
			newnode = lson[newnode];	root = lson[root];
		}
		else 
		{
			l = mid + 1;
			rson[newnode] = tot++;		lson[newnode] = lson[root];
			newnode = rson[newnode];	root = rson[root];
		}
		c[newnode] = c[root] + val;
	}
	return tmp;
}

int Query(int u,int v,int lca,int lca_root,int k)
{
	int l = 1,r = fuck;
	int pos = lower_bound(X+1,X+fuck,key[lca]) - X;
	while(l < r)
	{
		int mid = (l+r) >> 1;
		if(c[lson[u]] + c[lson[v]] - 2*c[lson[lca_root]] + (pos >= l && pos <= mid) >= k)
		{
			r = mid;
			u = lson[u];
			v = lson[v];
			lca_root = lson[lca_root];
		}
		else 
		{
			
			k -= c[lson[u]] + c[lson[v]] - 2*c[lson[lca_root]] + (pos >= l && pos <= mid);
			u = rson[u];
			v = rson[v];
			lca_root = rson[lca_root];
			l = mid + 1;
		}
	}
	return l;
}

int LCA(int u,int v)
{
	if(dfn[u] == dfn[v])
		return u;
	if(dfn[u] < dfn[v])
		swap(u,v);
	//if(dfn[fa[u][0]] <= dfn[v])
		//return LCA(fa[u][0],v);
	for(int i = 1;i >= 0;i++)
	{
		if(dfn[fa[u][i]] < dfn[v])
			return LCA(fa[u][i-1],v);
		if(dfn[fa[u][i]] == dfn[v])
			return v;
	}
}


void init()
{
	memset(first,-1,sizeof(first));
	memset(dfn,0,sizeof(dfn));
	dfn[1] = dep[1] = 0;
	tot = e = cnt = 0;
}

void dfs(int u,int pre)//          2       
{
	int pos = lower_bound(X+1,X+1+fuck,key[u]) - X;
	T[u] = Update(T[pre],pos,1);
	dfn[u] = ++cnt;
	dep[u] = dep[pre] + 1;
	fa[u][0] = pre;
	for(int j = 1;dep[u] - (1<= 0;j++)
		fa[u][j] = fa[fa[u][j-1]][j-1];
	for(int i = first[u];i != -1;i = nxt[i])
	{
		int v = vv[i];
		if(v == pre)	continue;
		dfs(v,u);
	}
}

int main()
{
	//freopen("in.txt","r",stdin);
	memset(fa,0,sizeof(fa));
	scanf_(n);scanf_(m);  
	init();
	for(int i = 1;i <= n;i++)
	{
		scanf_(key[i]);
		X[i] = key[i];
	}
	sort(X+1,X+1+n);
	fuck = unique(X+1,X+1+n) - X - 1;
	T[0] = build(1,fuck);
	for(int i = 1;i < n;i++)
	{
		int u,v;
		scanf_(u),scanf_(v);
		addedge(u,v);
	}
	dfs(1,0);
	while(m--)
	{
		int u,v,k;
		scanf_(u),scanf_(v),scanf_(k);
		int lca = LCA(u,v);
		printf("%d
",X[Query(T[u],T[v],lca,T[lca],k)]);
	}
	return 0;
}