CSP-S 2026 预测模拟卷（一）。原创训练，非官方试题。

时间限制：2.5 s 内存限制：512 MiB 分值：100 分

题目描述

给定一棵 n 个点的树，第 i 个点权值 ai。回答 q 次询问：给定 u,v,k，求 u 到 v 简单路径上的第 k 小点权。

输入格式

第一行 n,q。第二行 n 个 ai。接下来 n-1 行树边。接下来 q 行 u,v,k。

输出格式

每个询问输出一行答案。

样例 #1

5 3
5 1 7 3 9
1 2
1 3
2 4
2 5
4 3 2
4 5 2
3 5 3

3
3
7

数据范围

1<=n,q<=2*10^5；1<=ai<=10^9；保证 k 合法。

测试点配置

20 个等分测试点，每点 5 分；Subtask ID 从 0 开始，共 10 组，每组包含连续两个测试点。