题目背景

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）初赛，提供了额外 2.5 秒时限。

题解等资源可在 https://gitlink.org.cn/thusaa/thupc2026pre 查看。

よくまあここまで来た歴史を振り返ると
気が遠くなりそうになる だけど

荷物と遺伝子を乗せ一緒に揺られながら
行こうぜ この命は一瞬もいいところ

--- 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$ 的一组询问。

输出格式

输出到标准输出。

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

10 12 20
1 10
1 9
9 4
9 5
4 8
4 7
5 2
7 6
2 3
10 8 6 4 3 2 5 7 1 4 6 7
5 8 1
1 12 1
5 6 2
1 3 2
5 5 3
5 7 3
8 12 4
1 5 4
1 1 5
5 6 5
11 12 6
1 2 6
9 12 7
7 9 7
1 4 8
6 11 8
1 1 9
9 10 9
2 12 10
1 1 10

1
1
2
9
3
5
4
9
1
5
7
4
7
9
8
9
1
9
1
10

提示

【样例 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。

【提示】

本题提供了若干可供下载的样例，方便你的调试，请勿作大量无意义提交。