Duff in the Army

题意翻译

## 题目描述 Duff是一个军队中的一名士兵。Malek是**她**的上司。 他们在一个名为Andarz Gu的国家里,这个国家有 $n$ 个城市,分别编号 $1-n$ 。有 $n-1$ 条双向通行的道路联通整个国家。 一共有 $m$ 个人居住在这个国家中的一些城市里,每一个人有他的身份号(第 $i$ 个人的身份号是 $i$ )。注意,有可能有多个人居住在同一个城市,也有可能有些城市无人居住。 Malek喜欢对别人下命令,所以他让Duff回答他的q个提问,每一个提问包含三个数 $v$ , $u$ 和 $a$ 。 为了回答一个提问: 设想一共有 $x$ 个人居住在从城市 $u$ 到城市 $v$ (包含)的路径上,他们的身份号从小到大排序后分别是 $p_1,p_2,...,p_x$ 。如果设 $k=min(x,a)$ ,那么Duff应该按顺序告诉Malek $k,p_1,p_2,...,p_k$ 。从另一种说法来说,Malek想要知道在路径上身份编号前 $a$ 小的人(或者更少,如果这条路上总共居住的人少于 $a$ 个)。 Duff现在非常忙碌,所以她让你来帮助她回答Malek的提问。 ## 输入输出格式 ### 输入格式 输入的第一行包括3个整数, $n$ , $m$ 和 $q$ 。($1<=n,m,q<=10^5$ ) 接下来的 $n-1$ 行描述了连通城市的道路。每一行包括两个整数 $u$ 和 $v$ ,表示从城市 $u$ 到城市 $v$ 有一条双向道路。($1<=u,v<=n , u≠v$ ) 接下来的一行包括 $m$ 个正整数 $c_1,c_2,...,c_m$ , $c_i$ 表示编号为 $i$ 的人居住在城市 $c_i$ 里。($1<=c_i<=n$ ,对于每一个 $i$ 有 $1<=i<=m$ ) 接下来的 $q$ 行描述了Malek的提问。每一行包括三个正整数 $u$ , $v$ 和 $a$ ($1<=v,u<=n$ ,$1<=a<=10$ ,含义见题面) ### 输出格式 对于每一次提问,输出一行,包括 $k,p_1,p_2,...,p_k$ (含义见题面)。 感谢@星烁晶熠辉 提供的翻译

题目描述

Recently Duff has been a soldier in the army. Malek is her commander. Their country, Andarz Gu has $ n $ cities (numbered from $ 1 $ to $ n $ ) and $ n-1 $ bidirectional roads. Each road connects two different cities. There exist a unique path between any two cities. There are also $ m $ people living in Andarz Gu (numbered from $ 1 $ to $ m $ ). Each person has and ID number. ID number of $ i-th $ person is $ i $ and he/she lives in city number $ c_{i} $ . Note that there may be more than one person in a city, also there may be no people living in the city. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF587C/cba9f47daeeaa3fd35affca5736f451e21efdfbd.png)Malek loves to order. That's why he asks Duff to answer to $ q $ queries. In each query, he gives her numbers $ v,u $ and $ a $ . To answer a query: Assume there are $ x $ people living in the cities lying on the path from city $ v $ to city $ u $ . Assume these people's IDs are $ p_{1},p_{2},...,p_{x} $ in increasing order. If $ k=min(x,a) $ , then Duff should tell Malek numbers $ k,p_{1},p_{2},...,p_{k} $ in this order. In the other words, Malek wants to know $ a $ minimums on that path (or less, if there are less than $ a $ people). Duff is very busy at the moment, so she asked you to help her and answer the queries.

输入输出格式

输入格式


The first line of input contains three integers, $ n,m $ and $ q $ ( $ 1<=n,m,q<=10^{5} $ ). The next $ n-1 $ lines contain the roads. Each line contains two integers $ v $ and $ u $ , endpoints of a road ( $ 1<=v,u<=n $ , $ v≠u $ ). Next line contains $ m $ integers $ c_{1},c_{2},...,c_{m} $ separated by spaces ( $ 1<=c_{i}<=n $ for each $ 1<=i<=m $ ). Next $ q $ lines contain the queries. Each of them contains three integers, $ v,u $ and $ a $ ( $ 1<=v,u<=n $ and $ 1<=a<=10 $ ).

输出格式


For each query, print numbers $ k,p_{1},p_{2},...,p_{k} $ separated by spaces in one line.

输入输出样例

输入样例 #1

5 4 5
1 3
1 2
1 4
4 5
2 1 4 3
4 5 6
1 5 2
5 5 10
2 3 3
5 3 1

输出样例 #1

1 3
2 2 3
0
3 1 2 4
1 2

说明

Graph of Andarz Gu in the sample case is as follows (ID of people in each city are written next to them): ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF587C/0b4bff2f57d38ed14a5c0dfe241322d00c36fcd2.png)