시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 2217 | 848 | 673 | 39.495% |
현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민이는 힘이 좋기 때문에 현재 노드에서 거리가 $D$ 이하인 모든 노드에 전단지를 돌릴 수 있다.
날씨가 매우 덥기 때문에, 현민이는 최소한만 이동해서 목표를 달성하고 싶다! 현민이를 위해 현민이가 이동해야 하는 총 거리를 구해주자.
첫번째 줄에는 노드의 개수 $N$($ 1 \leq N \leq 100\ 000 $)과 케니소프트의 위치 $S$($ 1 \leq S \leq N $), 힘 $D$($ 0 \leq D \leq N $)이 주어진다.
두 번째 줄부터 $N$번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 $x$, $y$가 공백으로 구분되어 주어진다. 이는 $x$번 노드와 $y$번 노드가 연결되어 있음을 의미한다. ($1 \leq x, y \leq N$, $x \neq y$)
주어지는 연결관계는 트리를 구성하며, 모든 간선의 길이는 $1$이다.
현민이가 목표를 완수하기 위해 이동해야 하는 최소 거리를 출력하여라.
6 1 1 1 2 2 3 2 4 3 5 5 6
6
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2020 A번