暂无测试数据。

题目来源

递交题目请前往洛谷
链接:luogu P4866

描述

小K是一个十分喜欢二次元的宅男，所以他每天都在做梦，梦见一些二次元角色
小K的梦境是一个含有n个节点n-1条边的连通图，每个节点的编号从1到n，并且在一些节点上会有一个二次元角色
每个二次元角色都有 \(p_i和val_i\)两种属性,表示该角色所在节点编号和该角色给小K提供的愉悦值
在每次小K做梦时，他会从1号节点出发，每经过一条边需要消耗时间，小K每次做梦的时间是有限的,所以他想在有限时间内获得更多的愉悦值
在每次做梦结束的时候,小K必须回到1号节点,否则他会迷失在梦境中

输入

第一行三个整数n,m,T 分别表示图的节点数,二次元角色数和小K做梦的天数
接下来n-1行,每行3个整数u,v,t 表示节点u和节点v之间连有一条边,小K通过这条边需要t时间
接下来m行,每行两个整数 \(p_i和val_i\),表示节点 \(p_i\)有一个二次元角色,小K访问该节点时可以获得\(val_i\)的愉悦值
接下来T行,每行一个整数\(t_i\),表示这一天小K做梦的时间,小K必须在这个时间之内回到1号节点并获得尽可能多的愉悦值

输出

输出共T行,每行一个整数,依次表示小K每一天能获得的最大愉悦值

输入样例

7 3 3
1 2 2
1 3 1
2 4 1
2 5 10
3 6 1
6 7 2
4 5
5 50
7 7
1
10
100

输出样例

0
7
62

样例解释

由于作者较懒,请同学自己画图
第一天哪里都去不了
第二天走1->3->6->7->6->3->1获得最大愉悦值为7。
第三天可以所有地方都走一遍

数据范围与限制

对于20分的数据:\(n\leq1000,m\leq10\)
对于60分的数据:\(n\leq10^5,m\leq20,t_i\leq100\)
对于100分的数据:\(1\leq n\leq10^5,1\leq m\leq200,0\leq t_i\leq10^5,1\leq \sum val_i\leq10^9,1\leq t\leq50,1\leq T\leq10^5\),数据保证一个节点上最多只有一个二次元角色
时间限制1秒,空间限制256M