P14829 [THUPC 2026 初赛] Asian Soul

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛，提供了额外 2.5 秒时限。 题解等资源可在 查看。 よくまあここまで来た歴史を振り返ると 気が遠くなりそうになる だけど 荷物と遺伝子を乗せ一緒に揺られながら 行こうぜ この命は一瞬もいいところ --- **Asian Soul** by **Jun Maeda** & **MANYO** & **Yanaginagi**

给定一颗节点编号 $1, 2, \cdots, n$ 的树，其中根节点的编号为 $1$。 给定一个只包含 $1 \sim n$ 中整数的长度为 $m$ 的数列 $a_1, a_2, \cdots, a_m$，每个元素象征着树上对应编号的结点。 你要回答 $q$ 次询问。每次询问给定数列上的一个区间和树上的一个结点，查询在区间内选点和树上给定点求 LCA 后，所得到结点编号的最大值。 具体地，我们假设树上结点 $u, v$ 的 LCA 为 $\text{LCA}(u, v)$，则一组询问 $l, r, u$ 需要你求出 $\max_{l \leq k \leq r} \text{LCA}(a_k, u)$。

从标准输入读入数据。 第一行三个整数 $n, m, q$ ($1 \leq n, m, q \leq 5 \times 10^5$)。 接下来 $n-1$ 行，每行两个数 $u, v$，代表树上一条连接 $u, v$ 的边。 接下来一行 $m$ 个数，表示给定的数列 $a_1, a_2, \cdots, a_m$ ($1 \leq a_i \leq n$)。 接下来 $q$ 行，每行三个数 $l, r, u$ ($1 \leq l \leq r \leq m, 1 \leq u \leq n$)，表示关于数列上区间 $a_{l \sim r}$ 和树上结点 $u$ 的一组询问。

输出到标准输出。 对于每组询问依次输出一行一个数，表示对应询问的答案。

### 【样例 1 解释】 :::align{center}  ::: 树的形态如图所示。 ### 【样例 2】 见题目目录下的 2.in 与 2.ans。 ### 【样例 3】 见题目目录下的 3.in 与 3.ans。 ### 【样例 4】 见题目目录下的 4.in 与 4.ans。 ### 【样例 5】 见题目目录下的 5.in 与 5.ans。 ### 【样例 6】 见题目目录下的 6.in 与 6.ans。 ### 【样例 7】 见题目目录下的 7.in 与 7.ans。 ### 【样例 8】 见题目目录下的 8.in 与 8.ans。 ### 【样例 9】 见题目目录下的 9.in 与 9.ans。 ### 【样例 10】 见题目目录下的 10.in 与 10.ans。 ### 【提示】 本题提供了若干可供下载的样例，方便你的调试，请勿作大量无意义提交。