#P0836. 背包上树
背包上树
题目描述
给定一棵以节点 为根的树,树上共有 个节点(编号 )。每个节点 对应一件物品,每件物品只能使用一次。编号为的节点所对应的物品的重量为 ,基础价值为 ,珍惜度为 。
- 定义节点 的实际价值为 :$\displaystyle\text{val}(i) = v_i \times \left( \sum_{j \in \text{Subtree}(i)} \phi(a_j) \right)$ 。其中:
- 表示的欧拉函数,即中与互质的数的个数。
- 表示以为根的子树中的节点集合(包括本身)。
你需要从这 件物品中选择若干件放入一个容量为 的背包中,要求满足:
- 任意两个被选择的节点之间不能存在”祖先–后代“关系(即如果选择了某个节点 ,则不能选择它的祖先节点或任意后代节点)。
- 所选物品的总重量不能超过背包容量 。
请计算:
- 在满足条件的情况下,背包中所选物品可能的最大总实际价值。
- 一共有多少种不同的选择方案能够达到最大总实际价值。 如果两种方案所选择的节点集合不同,则认为是不同方案。由于方案数可能很大,请输出对 取模后的结果。
输入格式
本题包含多组测试数据。
第一行输入一个整数,测试数据组数。
对于每组测试数据,第一行输入两个整数,,分别表示节点数量和背包容量。
接下来行, 每行三个整数$w_i, v_i, a_i(1 \le w \le 10^9, 1 \le v_i \le 20, 1 \le a_i \le 10^6)$,分别表示编号为的节点所对应的物品的重量、基础价值、珍惜度。
接下来行,每行两个整数,表示树上的一条边(题目保证输入构成一棵树)。
对于所有测试数据,保证 。
输出格式
对于每组测试数据,输出一行两个整数:
- 最大总实际价值(题目保证最大总实际价值不会超过位有符号整数的表示范围)。
- 达到最大总实际价值的方案数(对取模)。
样例
2
5 5
2 3 6
2 2 4
1 4 5
2 1 3
1 2 2
1 2
1 3
2 4
2 5
3 2
2 4 2
1 5 3
1 5 3
1 2
1 3
33 1
20 2
提示
对于第一组测试数据,可行的最优选法为:只选节点。
对于第二组测试数据,可行的最优选法为:只选节点或选节点和节点。