UOJ Logo Sharp Sword 剑锋 OI

SSOI

#32. Duff 指挥官 Malek 的询问

统计

【问题描述】

  最近 Duff 当兵了,Malek 是她的指挥官。
  他们的国家 Andarz Gu 有 n 个城市(编号从 1 到 n),n - 1条双向道路。每一条道路连接着两个不同的城市。任何两个城市之间都存在一条唯一的路径。
Andarz Gu 国家中生活着 m 个人(从 1 到 m 编号)。每个人都有身份证号码,第 i 个人的身份证号码为 i,他/她所居住的城市编号为 Ci。注意,一个城市中可能不止一个人,也可能没有一个人住在这个城里。
  Malek 喜欢询问下属问题,这就是为什么他要 Duff 回答 Q 次询问的原因。在每一个询问,Malek给出三个数 u,v,a。
假设有 x 个人居住在从城市 u 到城市 v 路径上的城市(包括城市 u 和城市 v),这些人的身份证号码为 p1,p2,…,px(升序给出)。
设 k=min(x,a),Duff 应该回答一个序列 k,p1,p2,…,pk

【输入格式】

第一行三个整数 n,m,q(1≤ n,m,q≤ 10^5 )
接下来 n-1 行,每行两个整数 u 和 v,表示 u 和 v 之间有一条双向道路。(1≤ v,u≤ n,v≠ u)
接下一行 m 个整数 c1 ,c2 ,...,cm(1≤ ci ≤ n)
接下来 q 行表示 q 次询问,每行 3 个整数 u,v 和 a(1≤ v,u≤ n ,1≤ a≤ 10)

【输出格式】

对于每一个询问输出一个序列表示 k,p1,p2,…,pk 

【输入样例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

【时空限制】

4S
512MB

【子任务】

e0caf89368a4fcb9.png