AdditionalFile6995.zip

#6995. 「THUPC 2026 初赛」Asian Soul

标签: 传统 | 时间限制: 5000 ms | 内存限制: 1024 MiB |

题目背景

ょくまあここまで来た歴史を振り返ると 気が遠くなりそうになる だけど 荷物と遺伝子を乗せ一緒に揺られながら 行こうぜ この命は一瞬もいいところ －－－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 为 $\operatorname{LCA}(u, v)$ ，则一组询问 $l, r, u$ 需要你求出 $\max _{l \leq k \leq r} \operatorname{LCA}\left(a_{k}, u\right)$ 。

输入格式

从标准输入读入数据。

第一行三个整数 $n, m, q$ $\left(1 \leq n, m, q \leq 5 \times 10^{5}\right)$ 。

接下来 $n-1$ 行，每行两个数 $u, v$，代表树上一条连接 $u, v$ 的边。

接下来一行 $m$ 个数，表示给定的数列 $a_{1}, a_{2}, \cdots, a_{m}$ $\left(1 \leq a_{i} \leq n\right)$。

接下来 $q$ 行，每行三个数 $l, r, u$ $\left(1 \leq l \leq r \leq m, 1 \leq u \leq n\right)$ ，表示关于数列上区间 $a_{l \sim r}$ 和树上结点 $u$ 的一组询问。

输出格式

输出到标准输出。

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

样例 1

输入

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

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

提示

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

题目使用协议

来自 THUPC2026（2026年清华大学学生程序设计竞赛暨高校邀请赛）初赛。

以下『本仓库』皆指 THUPC2026 初赛 官方仓库（https://gitlink.org.cn/thusaa/thupc2026pre）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。