牛客/2025-8/D：圣诞树

题目描述

圣诞树上有 $n$ 个灯泡，通过 $(n-1)$ 根电线连接。每根电线连接两个不同的灯泡，使得所有灯泡形成一棵以第 $1$ 个灯泡为根的有根树。一开始圣诞树的美观度是 $0$，你可以点亮一些灯泡来提升美观度。

点亮第 $i$ 个灯泡需要消耗 $a_i$ 单位的电力，并会提升 $b_i$ 的美观度。对于第 $j$ 根电线，如果其连接的 $u_j$ 个灯泡和 $v_j$ 个灯泡都被点亮，则还会额外消耗 $c_j$ 单位的电力。为了安全起见，每个点亮的灯泡都必须通过电线与至少一个没有点亮的灯泡直接连接。

有一个量程为 $m$ 的电表，会显示总消耗电力对 $m$ 取模的结果。有 $q$ 次询问，每次询问给定 $r$ 和 $k$，你需要计算在只点亮以第 $r$ 个灯泡为根的子树里的灯泡、保持子树外灯泡不被点亮、且电表显示 $k$ 时圣诞树的最大美观度，以及达到该最大美观度的点亮方案数。

两种点亮方案不同，当且仅当存在至少一个灯泡在一种方案中被点亮而在另一种方案中未被点亮。方案数对 $10^9+7$ 取模。如果不存在可行方案，则最大美观度为 $-1$，方案数为 $0$。

输入输出格式

输入

第一行包含三个整数 $n,m,q$，表示灯泡个数、电表量程和询问个数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$。

接下来 $(n-1)$ 行，第 $j$ 行包含三个整数 $u_j,v_j,c_j$，表示电线连接关系与额外耗电。保证这些电线构成一棵树。

接下来 $q$ 行，每行包含两个整数 $r,k$，表示一次询问。

输出

输出 $q$ 行。每行两个整数，表示对应询问的最大美观度与达到最大美观度的方案数（对 $10^9+7$ 取模）。若无可行方案，输出 $-1\ 0$。

样例

4 4 4
1 1
2 2
3 3
4 4
1 2 1
1 3 2
2 4 3
1 0
1 1
1 2
1 3

4 1
5 2
2 1
7 1

1 2 2
1 1
1 0
1 1

0 1
-1 0

数据范围

• $1 \le n \le 100$
• $1 \le m \le 3 \times 10^4$
• $1 \le q \le 10^5$
• $1 \le a_i,b_i \le 10^6$
• $1 \le u_j,v_j \le n$
• $1 \le c_j \le 10^6$
• $1 \le r \le n$
• $0 \le k < m$