| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 768 MB | 106 | 32 | 27 | 41.538% |
You are given a weighted tree $T$ with $N$ nodes. The initial weight of the $i^{th}$ edge is $C_i,ドル but every day the weight changes by $A_i$. Thus, its weight will be $C_i + k * A_i$ in day $k$. Note that the weights might be negative.
The diameter of $T$ is defined as a the maximum distance between any two nodes. Note that because the weights might be negative, it is possible the two nodes determining the diameter are not distinct.
You will observe the tree for $D+1$ days, starting from day 0 until day $D$. You want to find a date which minimizes the diameter. Formally, you need to find an integer $x \in [0, D]$ such that no other integer in $[0, D]$ yields a smaller diameter. If there is more than one such integer, you should find a smallest such integer.
The first line contains the number of nodes $N,ドル and the number of observing days $D$.
Each of the next $N-1$ lines contains four integer $S_i, E_i, C_i, A_i,ドル which indicates edge $i$ connects two vertices $S_i$ and $E_i,ドル and it has cost $C_i$ in day 0ドル,ドル and it changes by $A_i$ everyday.
On the first line, print the integer $x \in [0, D]$ that minimizes the diameter in interval $[0, D]$. If there is more than one such integer, find a smallest such integer.
On the next line, print the diameter of tree in day $x,ドル when $x$ is the day you found in first line.
3 4 1 2 10 -2 2 3 20 2
0 30
At days 0ドル$ and 4ドル$ the tree will look like:
Note that the value of the diameter is the same $(30)$
The longest path is marked with red.
3 10 1 2 20 -3 2 3 30 -4
8 0
At days 0ドル$ and 8ドル$ the tree will look like:
Note that the value of the diameter at time $D=8$ is $(0)$ from the distance between node 1ドル$ and 1ドル$.
The longest path is marked with red.
5 5 1 2 20 -3 2 3 10 -3 3 4 22 -2 3 5 26 -3
5 23
At day 5ドル$ the tree will look like:
The longest path is marked with red.
4 0 1 2 -1 0 2 3 20 0 3 4 -1 0
0 20
At day 0ドル$ the tree will look like:
The longest path is marked with red.