#P0836. 背包上树

背包上树

题目描述

给定一棵以节点 11 为根的树,树上共有 nn 个节点(编号 1∼n1 \sim n)。每个节点 ii 对应一件物品,每件物品只能使用一次。编号为ii的节点所对应的物品的重量为 wiw_i,基础价值为 viv_i,珍惜度为 aia_i。

  • 定义节点 ii 的实际价值为 :$\displaystyle\text{val}(i) = v_i \times \left( \sum_{j \in \text{Subtree}(i)} \phi(a_j) \right)$ 。其中:
    • ϕ(x)\phi (x)表示xx的欧拉函数,即1∼x1\sim x中与xx互质的数的个数。
    • Subtree(u)Subtree(u)表示以uu为根的子树中的节点集合(包括uu本身)。

你需要从这 nn 件物品中选择若干件放入一个容量为 WW 的背包中,要求满足:

  • 任意两个被选择的节点之间不能存在”祖先–后代“关系(即如果选择了某个节点 uu,则不能选择它的祖先节点或任意后代节点)。
  • 所选物品的总重量不能超过背包容量 WW。

请计算:

  • 在满足条件的情况下,背包中所选物品可能的最大总实际价值。
  • 一共有多少种不同的选择方案能够达到最大总实际价值。 如果两种方案所选择的节点集合不同,则认为是不同方案。由于方案数可能很大,请输出对 109+710^9+7 取模后的结果。

输入格式

本题包含多组测试数据。

第一行输入一个整数T(1≤T≤2×105)T(1 \le T \le 2 \times 10^5),测试数据组数。

对于每组测试数据,第一行输入两个整数n(1≤n≤2×105)n(1 \le n \le 2 \times 10^5),W(1≤W≤106)W(1 \le W \le 10^6),分别表示节点数量和背包容量。

接下来nn行, 每行三个整数$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)$,分别表示编号为ii的节点所对应的物品的重量、基础价值、珍惜度。

接下来n−1n - 1行,每行两个整数u,v(1≤u,v≤n)u, v(1 \le u, v \le n),表示树上的一条边(题目保证输入构成一棵树)。

对于所有测试数据,保证 ∑(n×W)≤106\sum (n \times W) \le 10^6。

输出格式

对于每组测试数据,输出一行两个整数:

  • 最大总实际价值(题目保证最大总实际价值不会超过6464位有符号整数的表示范围)。
  • 达到最大总实际价值的方案数(对109+710^9 + 7取模)。

样例

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

提示

对于第一组测试数据,可行的最优选法为:只选节点11。

对于第二组测试数据,可行的最优选法为:只选节点11或选节点22和节点33。