시간 제한메모리 제한제출정답맞힌 사람정답 비율
12 초 1024 MB26141058.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$)

출력

하나의 정수로 문제의 정답을 출력하라.

예제 입력 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

예제 출력 1

110

예제 입력 2

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

예제 출력 2

3328

출처

  • 문제를 번역한 사람: koosaga