| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 32 | 21 | 19 | 63.333% |
마왕의 정체는 작년에 호반우가 키우던 애완용 트리였다. 트리는 여전히 어지러움을 느끼며 루트를 계속 바꾸고 있다. 이를 본 호반우는 트리의 루트를 통해서 신성한 물인 성수를 흘려보내 트리를 정화하려고 한다.
트리는 $N$개의 노드와 $N-1$개의 간선으로 이루어져 있으며 각 노드는 1ドル$번부터 $N$번까지의 번호가 정해져 있다. 1ドル ≤ i ≤ N$인 $i$에 대해 $i$번 노드는 양의 정수 $a_i$만큼 내부에 성수를 저장할 수 있는 공간을 가진다.
어떤 노드 $V$에 성수가 흘러 들어올 때 아래의 규칙을 따른다.
트리는 $M$번 노드의 공간이 성수로 가득 차면 정화되며 정화된 이후로는 더 이상 성수를 흘려보낼 수 없다고 한다.
트리의 루트가 계속 변해 어지러워하는 호반우에게 각 노드가 루트일 때 트리를 정화하기 위해 필요한 성수의 양을 알려주자!
첫 번째 줄에 트리의 노드 개수 $N$과 성수로 가득 차야 할 노드 번호 $M$이 공백을 두고 주어진다. $(1 ≤ M ≤ N ≤ 300,000円)$
두 번째 줄에 $N$개의 양의 정수 $a_{1},,円,円a_{2},,円,円a_{3},,円\cdots,,円a_{N}$이 공백을 두고 주어진다. $(1 ≤ a_{i} ≤ 10^{9})$
$a_{i}$는 $i$번 노드가 내부에 성수를 저장할 수 있는 공간의 크기이다.
세 번째 줄부터 $N-1$개의 줄에 걸쳐 트리의 각 간선이 연결하는 두 정점의 번호가 공백을 두고 주어진다.
$N$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번 노드가 루트일 때 트리가 정화되기 위해 루트로 흘려보낼 성수의 양을 출력한다.
5 2 5 8 3 9 12 1 2 2 3 4 2 1 5
32 37 34 28 20
1ドル$번 노드가 루트일 때를 생각해 봅시다. 트리는 위의 그림과 같습니다.
처음에 루트로 성수를 흘려주면 1ドル$번 노드에서 2ドル$번, 5ドル$번 노드로 성수가 흘러가며 2ドル$번 노드에서 3ドル$번, 4ドル$번 노드로 성수가 흘러가는 것을 알 수 있습니다.
이때 성수가 차게 되는 노드는 3ドル$번, 4ドル$번, 5ドル$번 노드이며 1ドル:1:2$ 비율로 내부가 성수로 채워지기 시작합니다.
이 중 3ドル$번 노드에 3ドル$만큼의 성수가 채워지면 4ドル$번, 5ドル$번 노드에는 3ドル,ドル 6ドル$만큼의 성수가 채워집니다.
3ドル$번 노드의 공간은 3ドル$이기에 성수로 가득 차게되고 2ドル$번 노드는 3ドル$번 노드가 가득 찼기에 4ドル$번 노드로만 성수를 흘려주어 4ドル$번, 5ドル$번 노드에 1ドル:1$ 비율로 성수가 채워집니다.
이후 4ドル$번 노드에 6ドル$만큼의 성수가 더 채워지면 5ドル$번 노드 역시 6ドル$만큼의 성수가 더 채워지며 두 노드는 동시에 성수로 가득 차게 됩니다.
이제 1ドル$번 노드에서는 5ドル$번 노드가 가득 찼기에 2ドル$번 노드로만 성수를 흘려주고 2ドル$번 노드는 모든 자식 노드가 성수로 가득 찼기에 2ドル$번 노드에 8ドル$만큼의 성수가 채워지며 트리가 정화됩니다.
트리가 정화될 때까지 2ドル$번, 3ドル$번, 4ドル$번, 5ドル$번 노드가 가득 찼기에 32ドル$만큼의 성수가 필요한 것을 알 수 있습니다.
6 3 2 7 4 3 10 12 1 2 3 2 4 2 2 5 6 5
8 12 38 12 18 9
5ドル$번 노드가 루트일 때를 생각해 봅시다. 트리는 위의 그림과 같습니다.
처음에 루트로 성수를 흘려주면 5ドル$번 노드에서 2ドル$번, 6ドル$번 노드로 성수가 흘러가며 2ドル$번 노드에서 1ドル$번, 4ドル$번 노드로 성수가 흘러가는 것을 알 수 있습니다.
이때 성수가 차게 되는 노드는 1ドル$번, 4ドル$번, 6ドル$번 노드이며 1ドル:1:2$ 비율로 내부가 성수로 채워지기 시작합니다.
이 중 1ドル$번 노드에 2ドル$만큼의 성수가 채워지면 4ドル$번, 6ドル$번 노드에는 2ドル,ドル 4ドル$만큼의 성수가 채워집니다.
1ドル$번 노드의 공간은 2ドル$이기에 성수로 가득 차게되고 2ドル$번 노드는 1ドル$번 노드가 가득 찼기에 3ドル$번, 4ドル$번 노드로 성수를 흘려주어 3ドル$번, 4ドル$번, 6ドル$번 노드에 1ドル:1:2$ 비율로 성수가 채워집니다.
이후 4ドル$번 노드에 1ドル$만큼의 성수가 더 채워지면 3ドル$번, 6ドル$번 노드는 1ドル,ドル 2ドル$만큼의 성수가 더 채워지며 4ドル$번 노드의 공간은 3ドル$이기에 성수로 가득 차게 됩니다.
이제 규칙에 따라 3ドル$번, 6ドル$번 노드에 1ドル:1$ 비율로 성수가 채워지며 3ドル$번 노드에 3ドル$만큼의 성수가 더 채워지면 6ドル$번 노드에도 3ドル$만큼의 성수가 더 채워지고 트리가 정화됩니다.
트리가 정화될 때까지 1ドル$번, 3ドル$번, 4ドル$번 노드가 가득 찼고 6ドル$번 노드는 9ドル$만큼 찼기에 18ドル$만큼의 성수가 필요한 것을 알 수 있습니다.
9 3 12 71 54 83 59 62 10 67 5 3 1 2 1 1 4 5 4 3 6 6 7 8 6 6 9
411 340 423 328 269 361 351 294 356
입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 대표적인 언어에 따른 빠른 입출력은 아래를 참고해 주세요.
cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 합니다. 줄 바꿈할 때는 endl 대신 ‘\n’을 사용해야 합니다.BufferedReader와 BufferedWriter를 사용해야 합니다.input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.University > 경북대학교 > 2023 Goricon G번