SPOJ Problem Set (classical)
10628. Count on a tree
Problem code: 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 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
我们在树上每个结点塞一个函数式线段树。
表示从这个节点到根的链所代表的权值线段树
则(u-v)=(u)+(v)-(lca(u,v))-(fa(lca(u,v)))
[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include