#P4182. [2015年湖南省队省队集训]Shopping

    ID: 3397 传统题 1000ms 128MiB 尝试: 641 已通过: 138 难度: 8 上传者: 标签>难度分类提高+/省选-树算法点分治动态规划依赖背包子树转区间单调队列优化多重背包CF2500

[2015年湖南省队省队集训]Shopping

[2015 湖南省队集训] Shopping

题目描述

小葱有 mm 元,要在由 nn 家商店组成的街区为小苗购买生日礼物。道路无向,连接成一棵树。第 ii 家商店只卖一种物品,每件价格为 cic_i,喜爱度为 wiw_i,最多可以买 did_i 件。

若在商店 uu 和 vv 都至少买了一件,那么在 uu 到 vv 的唯一路径上的每家商店也都必须至少买一件。允许什么都不买。

求总花费不超过 mm 时,所有购得物品的喜爱度之和最大是多少。购买同一商品的多件,每件的喜爱度单独计入。

输入格式

第一行一个整数 TT(1≤T≤51\le T\le5),表示数据组数。

每组第一行有两个整数 n,mn,m(1≤n≤5001\le n\le500,1≤m≤4 0001\le m\le4\,000)。接下来三行分别是 nn 个非负整数 wiw_i、nn 个正整数 cic_i、nn 个正整数 did_i,其中 0≤wi≤4 0000\le w_i\le4\,000,1≤di≤4 0001\le d_i\le4\,000。

接下来 n−1n-1 行,每行两个商店编号 u,vu,v,表示一条道路。商店编号从 11 到 nn。

输出格式

每组输出一行一个整数,表示最大的喜爱度之和。

样例 #1

样例输入 #1

1 
3 2
1 2 3
1 1 1
1 2 1
1 2
1 3

样例输出 #1

4