#P4182. [2015年湖南省队省队集训]Shopping
[2015年湖南省队省队集训]Shopping
[2015 湖南省队集训] Shopping
题目描述
小葱有 元,要在由 家商店组成的街区为小苗购买生日礼物。道路无向,连接成一棵树。第 家商店只卖一种物品,每件价格为 ,喜爱度为 ,最多可以买 件。
若在商店 和 都至少买了一件,那么在 到 的唯一路径上的每家商店也都必须至少买一件。允许什么都不买。
求总花费不超过 时,所有购得物品的喜爱度之和最大是多少。购买同一商品的多件,每件的喜爱度单独计入。
输入格式
第一行一个整数 (),表示数据组数。
每组第一行有两个整数 (,)。接下来三行分别是 个非负整数 、 个正整数 、 个正整数 ,其中 ,。
接下来 行,每行两个商店编号 ,表示一条道路。商店编号从 到 。
输出格式
每组输出一行一个整数,表示最大的喜爱度之和。
样例 #1
样例输入 #1
1
3 2
1 2 3
1 1 1
1 2 1
1 2
1 3
样例输出 #1
4