#Pmp112. 6.小明聚会

6.小明聚会

6.小明聚会

题目描述

小明住在 H 国的首都。H 国有n个城市,其中1号城市为其首都。城市间有n-1条单向道路。从任意一个城市出发,都可以沿着这些单向道路一路走到首都,从任何一个城市走到首都的路径是唯一的。

想要通过某一条道路,你必须使用一次过路券。H 国一共有m种过 路券,每张过路券以三个整数表示:v,k,w:你可以在城市v以价格w买到一张过路券。这张券可以使用k次。这意味着,拿着这张券通过了条道路之后,这张券就不能再使用了。

请注意你同一时间最多只能拥有最多一张过路券。但你可以随时撕掉手中已有的过路券, 并且在所在的城市再买一张。 小明家在首都。他有q位朋友,他希望把这些朋友们都邀请到他家做客。他想要知道每位朋友要花多少路费。他的朋友们永远都会选择一条花费最少的方式到达首都。

小明没有时间亲自计算出朋友们将要花费的路费。你可以帮帮他么?

输入格式

输入的第一行包含两个空格隔开的整数n和m,表示H国的城市数量和过路券的种数。输入的第一行包含两个空格隔开的整数n和m,表示 H 国的城市数量和过路券的种数。

之后的n−1行各自包含两个数ai和bi,代表城市ai到城市bi间有一条单向道路。之后的n-1行各自包含两个数a_i和b_i,代表城市a_i到城市b_i间有一条单向道路。

之后的m行每行包括三个整数vi,ki和wi,表示一种过路券。之后的m行每行包括三个整数v_i,k_i和w_i,表示一种过路券。

下一行包含一个整数q,表示小明朋友的数量。下一行包含一个整数q,表示小明朋友的数量。

之后的q行各自包含一个整数,表示小明朋友所在的城市。之后的q行各自包含一个整数,表示小明朋友所在的城市。

输出格式

输出共q行,每一行代表一位朋友的路费。

数据范围

(原站未提供,导入后需人工补齐)

样例

7 7 
3 1 
2 1 
7 6 
6 3 
5 3 
4 3 
7 2 3
7 1 1 
2 3 5
3 6 2
4 2 4 
5 3 10 
6 1 20 
3 
5 
6 
7 
10 
22 
5

提示

样例解释

对于第一位朋友,他在号5城市只能购买一种过路券,花费10元并且可以使用3次。这 足够他走到首都,因此总花费是10元。

对于第二位朋友,他在6号城市只能购买20元的过路券,并且只能使用一次。之后,他可以在3号城市购买2元,可以使用3次的过路券走到首都。总花费是22元。

对于第三位朋友,他在7号城市可以购买两种过路券。他可以花3元买一张可以使用2次的券,然后在3号城市再买一张2元,可以使用3次的券,走到首都。总花费是5元,而且其他的购买方式不会比这种更省钱。

对于40%的数据:n,m,q<=10,wi<=10n,m,q<=10,w_i<=10;

另有20%的数据:n,m,q<=500,wi<=100n,m,q<=500,w_i<=100;

另有20%的数据:n,m,q<=5∗103,wi<=103n,m,q<=5*10^3,w_i<=10^3;

对于100%的数据:1<=n,m,q<=105,1<=wi<=104,1<=vi,ki<=n1<=n,m,q<=10^5,1<=w_i<=10^4,1<=v_i,k_i<=n。