Description:


你得到一个带有N个节点的树。树节点从1编号到N,每个节点都有一个整数权重。
我们将要求您执行以下操作:
u v k:询问从节点u到节点v的路径上的第k个最小权重

Input:


在第一行中有两个整数N和M.(N,M <= 100000)
在第二行中有N个整数。第i个整数表示第i个节点的权重。
在接下来的N-1行中,每行包含两个整数u v,其描述边(u,v)。
在接下来的M行中,每行包含三个整数u v k,这意味着在从节点u到节点v的路径上询问第k个最小权重的操作。

Output:


对于每个操作,打印其结果。

Sample Input:


Output:


题解:


在树上构建主席树,如果没有接触过主席树,最好先去做一下这一道题:POJ2104 K-th Number
思路类似,按照dfs序插入,然后询问时左子树内元素多少为为val[ls[u]]+val[ls[v]]-val[ls[lca]]-val[ls[fa[lca]]]
需要求LCA,这里使用的LYQ的方法,具体介绍见各种LCA模板第四种。
代码如下: