Shopping
题目描述
马上就是小苗的生日了，为了给小苗准备礼物，小葱兴冲冲地来到了商店街。商店街有n个商店，并且它们之间的道路构成了一颗树的形状。
第i个商店只卖第i种物品，小苗对于这种物品的喜爱度是wi，物品的价格为ci，物品的库存是di。但是商店街有一项奇怪的规定：如果在商店u,v买了东西，并且有一个商店w在u到v的路径上，那么必须要在商店w买东西。小葱身上有m元钱，他想要尽量让小苗开心，所以他希望最大化小苗对买
到物品的喜爱度之和。这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为OI选手的你，你能帮帮他吗？
输入格式
输入第一行一个正整数T，表示测试数据组数。
对于每组数据，
第一行两个正整数n;m；
第二行n个非负整数w1,w2...wn；
第三行n个正整数c1,c2...cn；
第四行n个正整数d1,d2...dn；
接下来n-1行每行两个正整数u;v表示u和v之间有一条道路
输出格式
输出共T 行，每行一个整数，表示最大的喜爱度之和。
1
3 2
1 2 3
1 1 1
1 2 1
1 2
1 3
4
数据范围与约定
N<=500,M<=4000,T<=5,Wi<=4000,Di<=100