题目描述
Problem Background
Due to the negligence of the warden PF, the convict Little E found an opportunity to escape.
However, the uneducated Little E did not know how to keep things secret. Warden PF quickly discovered his plan and launched a pursuit.
Since Little E built his own boat, while Warden PF used an official boat, their performance on each waterway was different, and the travel times could vary. Details are provided in the Input Format.
To avoid going hungry, Little E plans to buy a bag to carry food.
Problem Description
Little E's escape route can be considered as passing through $n$ islands, connected by $n-1$ waterways.
Each island has ample supplies. Assuming he spends one unit of food for each day spent sailing on the sea. The unscrupulous boss stipulates that a backpack that can hold $k$ units of food will be sold for $k$ ten thousand yuan.
Warden PF can command the establishment of a bidirectional waterway between any two islands $u$ and $v$ where the travel time does not exceed $d$, and there are at least $q$ islands (excluding $u$ and $v$) on the waterway from island $v$ to island $u$. The travel time on this new waterway is $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$. Due to economic constraints, he can only build one additional waterway.
Little E can confirm the shortest time it takes for Warden PF to reach each island based on the official waterways (including the newly added waterway).
Warden PF will discover Little E's escape at time $t$ and start the pursuit.
To save money and escape Warden PF's pursuit, Little E wants you to help him write a program to calculate the minimum $k$ such that he can successfully escape to at least $l$ islands.
Supply replenishment does not take time, being caught in the middle counts as being caught, and arriving simultaneously does not count.
Replenishing supplies on the islands does not take time and can be done infinitely as long as the backpack can hold the supplies.
Problem Summary:
There are two people, $a$ and $b$, and a tree consisting of $n$ nodes. $a$ departs $t$ seconds earlier than $b$. If the travel time between two nodes does not exceed $d$, $b$ can build a waterway between these two nodes with a travel time of $\left\lfloor \dfrac{time(u \to v)}{2}\right\rfloor$. Find a plan that allows $a$ to reach at least $l$ nodes with the shortest time not longer than $b$, and under this condition, maximize the maximum distance between the islands.
Input Format
The first line contains five integers, $n, t, d, l, q$, representing the number of islands, the time Warden PF discovers the escape, the travel time range required for establishing a waterway, the minimum number of islands to be reached, and the number of intermediate islands required for establishing a waterway. Both their starting points are island $1$.
The next $n-1$ lines each contain four integers $u, v, p_i, e_i$, indicating that there is a road between island $u$ and island $v$. $p_i$ represents the time it takes for Little E to travel this waterway, and $e_i$ represents the time it takes for Warden PF to travel this waterway. The waterway is bidirectional.
Output Format
If there is a solution, output two lines.
The first line contains an integer $k$, representing the minimum amount of money (in ten thousand yuan) needed to escape.
The second line contains an integer $r$, representing the number of islands that can be reached with $k$ ten thousand yuan (island $1$ is also included).
If there is no solution, output "no solution" (quotes not needed).
Sample Input and Output
Sample Input #1
5 3 20 4 2
1 2 5 5
2 3 5 5
2 4 7 10
1 5 4 1
Sample Output #1
7
4
Sample Input #2
5 2 6 3 2
1 2 5 3
2 3 8 6
1 4 8 2
2 5 4 6
Sample Output #2
5
3
Sample Input #3
5 0 23 4 1
1 2 21 26
1 3 14 16
3 4 4 5
1 5 19 18
Sample Output #3
no solution
Notes/Hints
[Sample Explanation]
For Sample $1$, the final reachable points are $1, 2, 4, 5$, with the minimum cost being $7$. Since Warden PF from point $3\to 5$ would pass through points $5\to1\to2\to3$, which satisfies the condition of having at least $q$ intermediate points, Warden PF can connect points $3$ and $5$. If Warden PF chooses to connect $5\to3$, then the time to reach point $3$ would be $3+1+ \left\lfloor \dfrac{1+5+5}{2}\right\rfloor = 9$. However, the shortest time for Little E to reach point $3$ is $5 + 5 = 10$, which does not meet the condition, so regardless of the value of $k$, point $3$ is unreachable.
[Data Range]
| Test Case Number | $n\le$ | $t\le$ | $p_i,e_i\le$ | $d\le$ | Time Limit | Space Limit | Characteristics |
|---|---|---|---|---|---|---|---|
| $1$ | $10$ | $50$ | $50$ | $50$ | $1s$ | $128M$ | Adding edges does not affect the answer |
| $2$ | $16$ | $50$ | $50$ | $50$ | $1s$ | $128M$ | None |
| $3,4$ | $500$ | $500$ | $500$ | $500$ | $1s$ | $128M$ | Adding edges does not affect the answer |
| $5$ | $500$ | $500$ | $500$ | $500$ | $1s$ | $128M$ | $q = 0$ |
| $6,7$ | $500$ | $500$ | $500$ | $500$ | $1s$ | $128M$ | None |
| $8$ | $2.5 \times 10^3$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $128M$ | Adding edges does not affect the answer |
| $9,10$ | $2.5 \times 10^3$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $128M$ | $q = 0$ |
| $11 \sim 14$ | $2.5 \times 10^3$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $128M$ | None |
| $15$ | $2.5 \times 10^3$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $256M$ | None |
| $16$ | $7.5 \times 10^3$ | $10^8$ | $10^8$ | $10^8$ | $2s$ | $256M$ | None |
| $17$ | $7.5 \times 10^3$ | $10^8$ | $10^8$ | $10^8$ | $1s$ | $256M$ | None |
| $18 \sim 20$ | $7.5 \times 10^3$ | $10^8$ | $10^8$ | $10^8$ | $3s$ | $512M$ | None |
For $100\%$ of the data, $n\le 7.5\times 10^3$, $1\le l\le n$, $0\le t \le 10^8$, $0 \le u_i<v_i \le n$, $1\le p_i,e_i,d\le 10^8$, $0\le q\le 20$.
Guaranteed that the number of possible new bidirectional waterway schemes does not exceed $5 \times 10^6$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分