28134번 - 너의 집에 가까워졌어 너의 이름을 크게 불러봐도 너는 너무 멀어

너의 집에 가까워졌어 너의 이름을 크게 불러봐도 너는 너무 멀어

아무 의미 없어진 나의 산책 너가 묻은 길을 돌아보고 다시 길을 걸어

멀어 (feat. Beenzino) - Primary

현빈이와 수연이의 집은 너무 멀리 떨어져 있다. 이 둘이 사는 도시에는 $1$번 집부터 $N$번 집까지 총 $N$개의 집이 있다. 또, 서로 다른 두 집을 잇는 거리 $1$의 양방향 오솔길이 $N$개 있다. 임의의 두 집을 잇는 오솔길은 최대 한 개고, 임의의 두 집 사이에는 하나 이상의 오솔길을 이용하는 경로가 반드시 존재한다.

이 도시의 시장 민우는 오솔길 하나를 제거할 계획을 하고 있다. 민우는 현빈이와 수연이 같은 연인들의 왕래가 편했으면 한다. 따라서 오솔길 하나를 제거한 후에도 임의의 두 집 $u,v$ $(u<v)$ 사이의 경로가 존재하면서 모든 $(u,v)$ 쌍에 대한 거리의 합을 최소로 만들고 싶다.

민우와 이 도시의 연인들을 도와주자.

첫째 줄에 $N$이 주어진다. $(3\leq N \leq 200\,000)$

둘째 줄부터 $N$줄에 걸쳐 오솔길로 이어지는 두 집 $u$와 $v$가 공백으로 구분되어 주어진다. $(1\leq u,v \leq N; u\neq v)$

입력으로 주어지는 모든 값은 정수다.

문제의 조건을 만족하도록 한 개의 오솔길을 제거하였을 때 $\sum_{u<v}{d(u,v)}$의 최솟값을 출력하라. 이때, $d(u,v)$는 $u$번 집과 $v$번 집 사이의 거리를 의미한다.