Description

The country of Yaoyao-Yaoyao-Ba-Yiling has $n$ cities. They are connected by a magical communication tool — the “Senpai Talisman”. The Senpai Talisman of the $i$-th city is engraved with a positive integer $w_i$. There are $n-1$ roads among these $n$ cities. The $j$-th road connects city $u_j$ and city $v_j$, and has an attribute $t_j$. This road is denoted as $(u_j,v_j,t_j)$, where $t_j \in \{0,1,2\}$, meaning:

• When $t_j=0$, city $u_j$ and city $v_j$ are in an antagonistic relationship.
• When $t_j=1$, city $u_j$ and city $v_j$ are in an equal relationship.
• When $t_j=2$, city $u_j$ and city $v_j$ are in a friendly relationship.

Each road is bidirectional, and it is guaranteed that any two cities $u,v$ are mutually reachable.

Recently, Mars has suffered from the MARS-514 virus outbreak, so the construction of the Senpai Talisman system must be accelerated. We define:

• $w_i \in [1,R]$, and $w_i$ is a positive integer.
• For a road $(p,q,r)$, the following requirements must be satisfied:
  • When $r=0$, i.e., city $p$ and city $q$ are antagonistic, it must hold that $w_p \ne w_q$.
  • When $r=2$, i.e., city $p$ and city $q$ are friendly, it must hold that $w_p=w_q$.
  • When $r=1$, i.e., city $p$ and city $q$ are equal, there is no requirement on the relationship between $w_p$ and $w_q$.

After assigning values to $w_i$, treat $w_i$ as a sequence. Determine how many essentially different sequences $w_i$ can be formed.

In addition, the ruler of Yaoyao-Yaoyao-Ba-Yiling, Haoer Jiejie, found that the larger $w_i$ is, the more ink is needed, and the harder it is to build. Therefore, Haoer Jiejie wants to know the minimum possible value of the sum of $w_i$.

Note that, in this problem, sequences $A_i$ and $B_i$ are essentially the same if and only if for all $i$, $A_i=B_i$.

“Essentially different” means two sequences that are not essentially the same.

Brief statement:

• There is a tree with $n$ nodes. Node $i$ has a node weight $w_i$, and edge $j$ has an edge weight $t_j$.
• For each edge $(u_j,v_j,t_j)$, the endpoint node weights must satisfy:
  • $t_j=0$, $w_{u_j} \ne w_{v_j}$.
  • $t_j=1$, no requirement.
  • $t_j=2$, $w_{u_j}=w_{v_j}$.
  • For any node weight, $w_i \in [1,R]$.
• When $w_i$ is treated as a sequence, find (1) the number of essentially different sequences $w_i$, and (2) the minimum possible sum of $w_i$.

Input Format

The first line contains two integers $n,R$, representing the number of cities and the value range.

The next $n-1$ lines each contain three integers $u_j,v_j,t_j$, describing a road.

Output Format

Output one line with two integers: the number of essentially different sequences $w_i$ that satisfy the requirements, and the minimum possible sum of $w_i$.

If there is no essentially different sequence (i.e., the answer to the first question is $0$), then output $0$ for the second question as well.

Only the first answer is taken modulo $10^9+7$.

3 3
1 2 0
1 3 0

12 4

9 3
1 2 0
1 3 1
1 4 1
2 5 2
2 6 1
6 7 0
4 8 2
4 9 0

648 12

Hint

Explanation for Sample 1

The roads in the sample are distributed as follows:

There are $12$ assignment methods in total:

1. $w_i=\{1,2,2\}$.
2. $w_i=\{1,2,3\}$.
3. $w_i=\{1,3,2\}$.
4. $w_i=\{1,3,3\}$.
5. $w_i= \bf \{2,1,1\}$, this is the optimal case.
6. $w_i=\{2,1,3\}$.
7. $w_i=\{2,3,1\}$.
8. $w_i=\{2,3,3\}$.
9. $w_i=\{3,1,1\}$.
10. $w_i=\{3,1,2\}$.
11. $w_i=\{3,2,1\}$.
12. $w_i=\{3,2,2\}$.

Explanation for Sample 2

The roads in the sample are distributed as follows:

For the second question, one optimal assignment is: $w_i=\{2,1,1,1,1,1,2,1,2\}$.

Constraints and Notes

This problem uses bundled testdata.

• Subtask 1 (5 pts): $t_j=1$ or $t_j=2$.
• Subtask 2 (5 pts): $R=1$.
• Subtask 3 (10 pts): $u_j=j$, $v_j=j+1$.
• Subtask 4 (20 pts): $t_j=0$.
• Subtask 5 (10 pts): $n \le 10$, $R \le 5$.
• Subtask 6 (50 pts): no special constraints.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le R \le 100$.

For Subtask 1 ~ 5, $R \le 40$.

In the subtask descriptions above, $t_j=P$ means that for all $j \in [1,n)$, $t_j=P$.

For Subtask 1, “or” means that part of the test points in Subtask 1 satisfy $t_j=1$, and the other part satisfy $t_j=2$.

Translated by ChatGPT 5