자라는 나무

시간 제한5초메모리 제한768 MB

요약

간선 가중치가 날마다 일차식으로 변하는 트리에서 [0, D] 안에서 지름이 가장 작아지는 날과 그 지름을 구한다.

난이도: 어려움10점 중 9점
유형: 트리, 그리디, 그래프, 구현
정답자: 아직 제출이 없습니다

문제

가중치가 있는 트리 $T$ 가 주어진다. 노드의 수는 $N$ 이다. $i$ 번째 간선의 초기 가중치는 $C\_i$ 이고, 하루가 지날 때마다 $A\_i$ 만큼 변한다. 따라서 $k$ 일째에 이 간선의 가중치는 $C\_i + k \* A\_i$ 이다. 가중치는 음수가 될 수도 있다.

$T$ 의 지름은 두 노드 사이의 최대 거리로 정의한다. 가중치가 음수가 될 수 있으므로, 지름을 결정하는 두 노드가 서로 같을 수도 있다.

0일부터 $D$ 일까지, $D+1$ 일에 걸쳐 트리를 관찰한다. 지름을 최소로 만드는 날짜를 찾으려고 한다. 정확히 말해, $[0, D]$ 에 속한 다른 어떤 정수도 더 작은 지름을 만들지 않는 정수 $x \in [0, D]$ 를 찾아야 한다. 그러한 정수가 여러 개라면 가장 작은 것을 찾는다.

입력

첫째 줄에 노드의 수 $N$ 과 관찰 일수 $D$ 가 주어진다.

다음 $N-1$ 개 줄에 각각 네 개의 정수 $S\_i, E\_i, C\_i, A\_i$ 가 주어진다. 이는 $i$ 번째 간선이 두 정점 $S\_i$ 와 $E\_i$ 를 연결하고, 0일째의 비용이 $C\_i$ 이며, 매일 $A\_i$ 만큼 변한다는 뜻이다.

출력

첫째 줄에 구간 $[0, D]$ 에서 지름을 최소로 만드는 정수 $x \in [0, D]$ 를 출력한다. 그러한 정수가 여러 개라면 가장 작은 것을 출력한다.

둘째 줄에 첫째 줄에서 찾은 날 $x$ 일째 트리의 지름을 출력한다.

제한

$1 \leq N \leq 250\ 000$
$0 \leq D \leq 10^6$
$1 \leq S\_i, E\_i \leq N$
$|C\_i| \leq 10^8$
$|A\_i| \leq 10^3$

예제4

예제 1
입력
```
3 4
1 2 10 -2
2 3 20 2
```
예상 출력
```
0
30
```
예제 2
입력
```
3 10
1 2 20 -3
2 3 30 -4
```
예상 출력
```
8
0
```

예제 3

입력

예상 출력

5
23

예제 4
입력
```
4 0
1 2 -1 0
2 3 20 0
3 4 -1 0
```
예상 출력
```
0
20
```