시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB (추가 메모리 없음) | 217 | 70 | 49 | 32.237% |
정휘는 정점이 $N$개인 트리와 길이가 $N$인 수열을 갖고 있다. 트리의 각 정점에는 정수가 하나씩 적혀 있으며, 각 간선은 1 이상 20만 이하의 자연수로 표현되는 색깔 중 하나로 칠해져 있다.
정휘는 트리와 수열을 따로 구분해야 하는 게 귀찮아서, 트리의 정점과 수열의 원소를 일대일대응시키는 방식으로 트리와 수열을 합치기로 했다. 물론 그냥 합치는 건 재미가 없으니, 트리와 수열을 합칠 때의 점수를 아래와 같이 정의하기로 했다.
예를 들어, 아래 트리는 4개의 구역으로 나누어진다.
그리고, 만약 정휘가 아래와 같은 방식으로 수열과 트리를 합친다면, 아래와 같은 102점을 얻게 된다.
정휘는 트리와 수열을 합칠 때 얻을 수 있는 점수의 최솟값과 최댓값이 궁금해졌지만, 트리와 수열의 크기가 너무 커서 계산하지 못하고 있다. 컴퓨터를 잘 다루는 여러분들이 정휘를 도와 얻을 수 있는 점수의 최솟값과 최댓값을 구해보자.
첫째 줄에 트리의 정점의 개수와 수열의 길이를 의미하는 정수 $N$이 주어진다. ($2 \leq N \leq 200\,000$)
둘째 줄부터 $N-1$개의 줄에 걸쳐, 트리의 간선을 의미하는 세 정수 $v_i, w_i, c_i$가 한 줄에 하나씩 공백으로 구분되어 주어진다. 이는 $v_i$번 정점과 $w_i$번 정점을 연결하는 간선의 색깔이 $c_i$라는 것을 의미한다. ($1 \leq v_i, w_i \leq N$, $1 \leq c_i \leq 200\,000$)
다음 줄에는 트리의 $1, 2, \cdots, N$번 정점에 적힌 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($-1\,000 \leq A_i \leq 1\,000$)
다음 줄에는 길이가 $N$인 수열의 원소를 나타내는 정수 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다. ($-1\,000 \leq B_i \leq 1\,000$)
첫째 줄에 정휘가 얻을 수 있는 점수의 최솟값을 출력한다.
둘째 줄에 정휘가 얻을 수 있는 점수의 최댓값을 출력한다.
8 1 2 1 2 5 1 2 4 3 5 6 2 6 3 2 6 8 2 8 7 1 5 -3 4 -1 1 0 -1 2 2 -2 0 -1 0 4 6 1
-51 122
High School > 선린인터넷고등학교 > 제6회 천하제일 코딩대회 본선 C번