P8971 "GROI-R1" Rainbow Higanbana

A boy wears a dark gray spring school uniform jacket and black shorts, with a clean white shirt inside. For some reason, his right hand is wrapped in bandages, and his right eye is tightly covered by his hair, giving off a mysterious feeling. A bright red higanbana petal spins above the classroom, where no one pays attention. Qi’s background is always a mystery. "So who are you, and why did you come here!" But the higanbana clearly does not want you to know any of that.

Qi gave Han a tree numbered $1\sim n$. Each node originally had a node value, and some edges have edge weights while others do not. However, Qi erased the node values. Han only knows that **all node values are integers, and are between $l$ and $r$ (inclusive)**. Also, node values and edge weights satisfy the following special relationship: - For **edges with edge weights**, the **sum of the node values of the two endpoints must equal the edge weight**. - For **edges without edge weights**, there is **no restriction**. Qi asks Han **how many different ways there are to fill in the node values**. Two fillings are different if and only if there exists at least one node whose value is different. However, Han cannot solve this problem. Han asks you to solve it.

**This problem has multiple test cases.** The first line contains an integer $T$, representing the number of test cases. For each test case: The first line contains three integers $n,l,r$, meaning the tree has $n$ nodes, and the node value range is $[l,r]$. The next $n-1$ lines each start with an integer $op$. If $op=0$, this edge has no edge weight; if $op=1$, this edge has an edge weight. + If $op=0$, then input two integers $u,v$, meaning this edge connects nodes $u,v$. + If $op=1$, then input three integers $u,v,w$, meaning there is an edge of weight $w$ connecting nodes $u,v$.

For each test case, output one integer per line, representing the number of ways to fill in the node values. The answer should be taken modulo $10^9+7$.

**Sample Explanation** For the first test case in the sample, we can get the following graph:  The $5$ filling methods are: $\{0,2,2,0,0,3\}\\\{0,2,2,0,1,3\}\\\{0,2,2,0,2,3\}\\\{0,2,2,0,3,3\}\\\{0,2,2,0,4,3\}$ It can be proven that no other filling methods exist. In the sample input, blank lines were added for readability. In the actual testdata, there are no extra blank lines. **Constraints** **This problem uses bundled tests.** | Subtask ID | Constraints | Special Property | Score | | :-----------: | :-----------: | :-----------: | :-----------: | | $\text{Subtask1}$ | $1\le n\le 10$，$0\le l,r\le5$ | | $15$ | | $\text{Subtask2}$ | $1\le n\le 2\times 10^5$，$0\le l,r\le5$ | | $20$ | | $\text{Subtask3}$ | $1\le n\le 10$，$-10^9\le l,r\le 10^9$ | | $15$ | | $\text{Subtask4}$ | $1\le n\le 2\times10^5$，$-10^9\le l,r\le 10^9$ | Yes | $10$ | | $\text{Subtask5}$ | $1\le n\le 2\times10^5$，$-10^9\le l,r\le 10^9$ | | $40$ | Special Property: It is guaranteed that every edge has no edge weight. For $100\%$ of the data, it is guaranteed that $1\le T \le 5$, $1\le n\le 2\times10^5$, $1\le \sum n\le 10^6$, $-10^9\le l\le r \le 10^9$, $-10^9\le w\le 10^9$, $op\in\{0,1\}$. Translated by ChatGPT 5