#P16207. [SEUSA 2025 Div 1]Tree Racing树上赛车

[SEUSA 2025 Div 1]Tree Racing树上赛车

题目描述

有一条赛车赛道,由 nn 个检查点组成,检查点之间通过 n−1n-1 条长度为 1 的隧道连接,整体构成一棵树。

比赛开始前,有 mm 名赛车手分别出生在不同的检查点,他们的目标是沿最短路到达终点检查点。每名赛车手通过一条单位长度隧道所需时间不同,且速度保持不变。

某些检查点是特殊检查点,每个特殊检查点只允许最快到达的 kk 名赛车手通过。若多名赛车手同时到达,则速度更快者优先通过。若赛车手出生在特殊检查点,则视为已经立即通过该检查点,并计入这 kk 名之中。

请预测每名赛车手到达终点所需时间;若会被某个特殊检查点淘汰,则输出 -1。

输入格式

第一行包含三个整数 n,m,kn,m,k:

$$2\le n\le 2\cdot 10^5, \qquad 1\le m\le n-1, \qquad 1\le k\le 10.$$

接下来 n−1n-1 行,每行包含两个整数 a,ba,b,表示一条隧道连接检查点 a,ba,b。

接下来 mm 行,第 ii 行包含两个整数 p,tp,t,表示第 ii 名赛车手出生在检查点 pp,并且通过一条单位长度隧道需要 tt 秒。

保证没有两名赛车手出生在同一检查点,没有赛车手出生在终点,且所有 tt 互不相同。

接下来一行包含一个整数 ee,表示终点检查点。

接下来一行包含一个整数 cc,表示特殊检查点数量。

接下来 cc 行,每行一个整数 xx,表示检查点 xx 是特殊检查点。保证 x≠ex\ne e,且所有特殊检查点互不相同。

输出格式

输出 mm 行,第 ii 行表示第 ii 名赛车手到达终点所需秒数;若该赛车手会被淘汰,则输出 -1。

样例 #1

输入

8 5 2
2 1
1 3
4 5
1 4
4 6
6 7
6 8
5 2
3 4
6 3
7 1
8 5
2
2
1
6

输出

6
-1
-1
4
-1