P8290 [NOI Qualifier Joint Contest 2022] Filling the Tree

The original time limit is 2 s.

There is an undirected tree with $n$ nodes. Initially, the weight of every node is $0$. KK wants to make some modifications to this tree. He will pick any node as the initial current node, and then repeat the following actions: 1. Change the weight of the current node $i$ to a **positive integer** $x$, which must satisfy $l_i \leq x \leq r_i$. Here $l_i, r_i$ are two positive integers given in the input. 2. End the modification process, or move to a node adjacent to the current node whose weight is $0$ (if no such node exists, he must end the modification process). Now KK has two questions: 1. After the modifications end, how many different trees can be obtained such that the difference between the maximum and minimum among all **non-zero weights** on the tree is at most $K$? Here $K$ is a positive integer given in the input. 2. What is the sum of the weights of all such trees? (The weight of a tree is defined as the sum of the weights of all nodes on the tree.) You need to output the answers to these two questions modulo $10^9 + 7$. We consider two trees different if and only if there exists at least one node whose weight is different. Friendly notes: 1. KK will modify at least one node (the initial node). 2. In essence, KK will modify an arbitrary path in the tree, and in the end it must satisfy that the difference between the maximum and minimum weights on this path is at most $K$.

The first line contains two positive integers $n, K$, representing the number of nodes and the maximum allowed difference between weights. The next $n$ lines each contain two positive integers $l_i, r_i$, representing the minimum and maximum possible weight of node $i$ after being modified. The next $n - 1$ lines each contain two positive integers $u_i, v_i$, indicating that there is an edge between node $u_i$ and node $v_i$. The input guarantees that these edges form a tree.

Output two lines, each containing one integer, representing the answers to the first question and the second question modulo $10^9 + 7$, respectively. Note that if you do not plan to answer the second question, you may output any integer on the second line. If the output file contains only one line, you may get $0$ points due to an invalid format.

**[Sample Explanation #1]** | | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ | $14$ | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | Node $1$ | $2$ | $3$ | $2$ | $3$ | $3$ | $3$ | $3$ | $3$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | | Node $2$ | $0$ | $0$ | $3$ | $3$ | $4$ | $0$ | $4$ | $3$ | $3$ | $4$ | $5$ | $0$ | $0$ | $0$ | | Node $3$ | $0$ | $0$ | $0$ | $0$ | $0$ | $4$ | $4$ | $4$ | $0$ | $0$ | $0$ | $4$ | $5$ | $6$ | The table lists all $14$ trees that satisfy the condition. The sum of the weights of these trees is $78$. **[Constraints]** For $100\%$ of the data, $1 \leq n \leq 200$, $1 \leq l_i \leq r_i \leq {10}^9$, $1 \leq K \leq {10}^9$. | Test Point | $n \leq $ | $r_i, K \leq$ | Other Constraints | |:-:|:-:|:-:|:-:| | $1$ | $5$ | $10$ | None | | $2$ | $30$ | $10^9$ | None | | $3$ | $30$ | $10^9$ | None | | $4$ | $30$ | $500$ | None | | $5$ | $200$ | $200000$ | None | | $6$ | $200$ | $200000$ | None | | $7$ | $200$ | $10^9$ | A | | $8$ | $200$ | $10^9$ | A | | $9$ | $200$ | $10^9$ | None | | $10$ | $200$ | $10^9$ | None | Special constraint A: all nodes form a chain, and there is an edge between the node numbered $i$ and the node numbered $i + 1$. **[Scoring]** This problem has $10$ test points, each worth $10$ points. Answering the first question correctly gives $7$ points, and answering the second question correctly gives $3$ points. Translated by ChatGPT 5