시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
12 초 | 1024 MB | 26 | 14 | 10 | 58.824% |
$N$ 개의 정점으로 이루어진 트리 $T_1$ 가 있다. $T_1$의 각 정점에는 1부터 $N$까지의 번호가 부여되어 있고, 각 간선에는 정수 가중치 (음수일 수 있음) 가 부여되어 있다. $T_1$ 에서 두 정점 간의 거리의 최댓값을 트리의 지름이라고 한다. 이 때 두 정점은 같은 정점일 수 있다.
실습에서 이 문제를 접한 구재현 학생은 다음과 같은 풀이를 생각했다. 트리의 루트를 1번 정점으로 두었을 때, 두 정점 $x, y$ 간의 거리는
$depth_1(x) + depth_1(y) - depth_1(LCA_1(x, y)) - depth_1(LCA_1(x, y))$
이다. 이 때 $depth_1(x)$ 는 $T_1$ 에서 루트와 정점 $x$ 의 거리이고, $LCA_1(x, y)$ 는 $T_1$ 에서 두 정점 $x, y$ 의 LCA이다. 구재현 학생은 Sparse Table을 사용해서 LCA를 $O(\log N)$ 에 구할 수 있다. 고로, 모든 $1 \le x, y \le N$ 에 대해서 해당 값의 최댓값을 구하면 $O(N^2 \log N)$ 에 문제를 해결할 수 있다.
구재현 학생은, 이 알고리즘을 구현하고 시간 초과를 받았다. 자존심이 상한 구재현 학생은, 위 문제를 조금 바꿔서 코치들에게 도전하기로 하였다. $T_2$를 $T_1$ 과 동일한 형식으로 주어지는 트리라고 하고, $depth_2(x), LCA_2(x, y)$ 역시 비슷하게 정의 할 때, 다음 값을 계산하자:
$\max_{1 \le x, y \le N} (depth_1(x) + depth_1(y) - depth_1(LCA_1(x, y)) - depth_2(LCA_2(x, y)))$
훌륭한 코치인 여러분 역시 자존심이 강하다. 이 문제를 풀어서, 하라는 공부는 안하고 이상한 자료구조 문제나 만드는 구재현 학생의 콧대를 꺾어주자.
첫 번째 줄에 두 트리의 정점 수 $N$ ($1 \le N \le 400\,000$) 이 주어진다.
이후 $N-1$ 개의 줄에 세 정수 $u_i, v_i, w_i$ 가 주어진다. $T_1$ 에 두 정점 $u_i, v_i$ 를 잇는 가중치 $w_i$ 의 간선이 있음을 뜻한다. ($1 \le u_i, v_i \le N, |w_i| \le 2^{31} - 1$)
이후 $N-1$ 개의 줄에 세 정수 $u_i, v_i, w_i$ 가 주어진다. $T_2$ 에 두 정점 $u_i, v_i$ 를 잇는 가중치 $w_i$ 의 간선이 있음을 뜻한다. ($1 \le u_i, v_i \le N, |w_i| \le 2^{31} - 1$)
하나의 정수로 문제의 정답을 출력하라.
5 1 2 10 2 4 20 3 4 30 4 5 50 1 2 15 1 3 25 1 4 35 1 5 25
110
9 5 7 6577 4 5 -8869 5 9 9088 2 1 -124 6 2 410 2 8 -8154 4 8 4810 3 4 -4268 3 9 763 6 2 -8959 7 4 7984 3 8 -504 8 6 9085 5 2 -4861 1 9 8539 1 7 -7834
3328