레이팅 미적용\(N\) (\(2 \le N \le 2\cdot 10^5\))개의 목초지가 \(N-1\)개의 도로로 연결되어 트리를 이룬다. 모든 도로는 건너는 데 1초가 걸린다. 각 목초지의 풀은 0에서 시작하고, \(i\)번째 목초지의 풀은 초당 \(a_i\) (\(1\le a_i\le 10^8\)) 단위씩 자란다. 농부 존은 처음에 목초지 1에 있고, 돌아다니면서 모든 목초지의 풀에 비료를 주어야 한다. 풀이 \(x\) 단위만큼 자란 목초지를 방문하면 비료가 \(x\)만큼 필요하다. 목초지는 처음 방문할 때만 비료를 주면 되고, 비료를 주는 데는 시간이 걸리지 않는다.
입력에는 추가 매개변수 \(T\in \{0,1\}\)이 주어진다.
- \(T=0\)이면 농부 존은 목초지 1에서 끝나야 한다.
- \(T=1\)이면 농부 존은 아무 목초지에서나 끝나도 된다.
모든 목초지에 비료를 주는 데 걸리는 최소 시간과, 그 시간 안에 끝내기 위해 필요한 비료의 최소량을 계산한다.
출제자: Rohin Garg
배점
- 입력 3-10: \(T=0\)
- 입력 11-22: \(T=1\)
- 입력 3-6 및 11-14: 어떤 목초지도 세 개를 초과하는 도로와 인접하지 않는다.
출제자: Rohin Garg
첫째 줄에 \(N\)과 \(T\)가 주어진다.
그다음 \(2\)부터 \(N\)까지의 각 \(i\)에 대해 \(p_i\)와 \(a_i\)가 주어지는 줄이 있는데, 이는 목초지 \(p_i\)와 \(i\)를 연결하는 도로가 있음을 의미한다. \(1\le p_i
최소 시간과 최소 비료량을 공백으로 구분하여 출력한다.
5 0
1 1
1 2
3 1
3 48 21The optimal route for Farmer John is as follows:
- At time \(1\), move to node \(3\), which now has \(1 \cdot 2 = 2\) grass and so needs \(2\) fertilizer.
- At time \(2\), move to node \(5\), which now has \(2 \cdot 4 = 8\) grass and so needs \(8\) fertilizer.
- At time \(3\), move back to node \(3\), which we already fertilized and so don't need to fertilize again.
- At time \(4\), move to node \(4\), which now has \(4 \cdot 1 = 4\) grass and so needs \(4\) fertilizer.
- At time \(5\), move back to node \(3\), which we already fertilized.
- At time \(6\), move back to node \(1\).
- At time \(7\), move to node \(2\), which now has \(7 \cdot 1 = 7\) grass and so needs \(7\) fertilizer.
- At time \(8\), return to node \(1\).
This route takes \(8\) time and uses \(2 + 8 + 4 + 7 = 21\) fertilizer. It can be
shown that \(8\) is the least possible amount of time for any route that returns
to node \(1\) at the end and \(21\) is the least possible fertilizer used for any
route that returns to node \(1\) and takes \(8\) time.
5 1
1 1
1 2
3 1
3 46 29The optimal route for Farmer John is as follows:
- At time \(1\), move to node \(2\), which now has \(1 \cdot 1 = 1\) grass and so needs \(1\) fertilizer.
- At time \(2\), move back to node \(1\).
- At time \(3\), move to node \(3\), which now has \(3 \cdot 2 = 6\) grass and so needs \(6\) fertilizer.
- At time \(4\), move to node \(5\), which now has \(4 \cdot 4 = 16\) grass and so needs \(16\) fertilizer.
- At time \(5\), move back to node \(3\), which we already fertilized and so don't need to fertilize again.
- At time \(6\), move to node \(4\), which now has \(6 \cdot 1 = 6\) grass and so needs \(6\) fertilizer.
This route takes \(6\) time and uses \(1 + 6 + 16 + 6 = 29\) fertilizer. It can be
shown that \(6\) is the least possible amount of time for any route and \(29\) is
the least possible fertilizer used for any route that takes \(6\) time.
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > February > Gold