Skip to content

14224: 【原4224】硬核战棋

题目

题目描述

author: MoLe 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4224

Description

MoLe非常喜欢玩一款硬核战棋游戏,这款游戏的地图可以被简化为一个拥有\(n\)个节点的树,节点的编号为\(1 \sim n\)。地图上总共有\(m\)名敌人,这些敌人都处在地图的某个节点上(注意,一个节点上可能会有多个敌人),而第\(i\)名敌人的战力为\(i\)。

游戏一共有\(q\)个回合,每一回合游戏会给定一条从节点\(u\)到节点\(v\)的简单路径,并要求你消灭这条简单路径上的至多\(k\)名敌人,你可以获得等同于你消灭敌人数量的分数,然后在回合结束时,所有的敌人都会在原地重生,如此往复。

由于得到的分数仅与消灭敌人的数量有关,MoLe当然希望每次他要面对的敌人战力都尽量的低,现在给你一张地图,以及每个回合游戏给出的限制,你需要输出每个回合,MoLe最多可以消灭多少敌人,以及从小到大输出该路径上战力最低的需要消灭的敌人。

Input Format

第一行三个整数\(n, m, q\)

接下来\(n-1\)行,每行\(2\)个整数\(u, v\)代表编号为\(u\)的点和编号为\(v\)的点之间有一条无向边

接下来\(1\)行,共\(m\)个整数,第\(i\)个整数代表第\(i\)名敌人所在的节点位置

接下来\(q\)行,每行\(3\)个整数 \(u,v,k\) 代表游戏该回合给出的限制条件

Output Format

输出共\(q\)行,每行第一个整数\(a\)代表能够消灭的最大敌人数,接下来从小到大地输出\(a\)个整数,代表需要消灭的敌人的战力。

Sample Input

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

Sample Output

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

Limits

对于\(30 \% \)的数据,保证\(n \leq 100, m \leq 100, q \leq 100\)

对于另外\(30 \% \)的数据,保证\(k = 1\)

对于\(100 \% \)的数据,保证\(n \leq 10^5, m \leq 10^5, q \leq 10^5, k \leq 10\)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!