유전자 트리

유전자 트리는 여러 유전자나 생물 종의 진화를 나타내는 트리다. 유전자 트리는 잎 노드에 저장된 특정 유전자들의 연관성을 계통에 대한 가정 없이 표현한다. 잎 노드는 분류군(taxa)이라 부르는 유전자를 나타내고, 내부 노드는 추정되는 조상 분류군을 나타낸다. 트리의 각 간선에는 두 노드 사이의 진화적 거리를 나타내는 양의 정수인 계통 길이(phylogenetic length)가 부여된다. 예를 들어 아래 왼쪽 그림은 여섯 개의 잎 노드를 가진 유전자 트리로 여섯 분류군 사이의 관계를 근사하며, 오른쪽 그림은 네 개의 분류군을 가진 유전자 트리를 보여준다.

Figure B.1: 뿌리 없는 유전자 트리 T1과 T2.

위의 T1과 T2처럼, 유전자 트리는 모든 내부 노드(잎이 아닌 노드)의 차수가 3인 뿌리 없는 트리로 모델링된다. 두 잎 노드 사이의 경로 길이는 두 노드 사이의 유일한 경로에 있는 간선들의 계통 길이의 합이다. T1에서 Human과 Cow 사이의 경로 길이는 2 + 3 = 5이고, Human과 Goldfish 사이의 경로 길이는 2 + 4 + 8 + 10 = 24이다. 이 길이들은 Human이 Goldfish보다 Cow에 유전적으로 훨씬 가깝다는 것을 보여준다. T2에서 Human과 가장 가까운 영장류는 Chimpanzee라고 추측할 수 있다.

연구자들은 트리에서 유전자 사이의 거리를 측정하는 데 관심이 있다. 잘 알려진 거리 척도는 모든 순서 없는 잎 쌍에 대한 경로 길이의 제곱의 합이다. 더 정확하게, 그러한 거리 d(T)는 다음과 같이 정의된다:

[d(T) = \sum_{\text{unordered pair } (u, v)}{p^2_{u, v}}]

여기서 p**u,v는 T에서 두 잎 노드 u와 v 사이의 경로 길이이다. d(T)는 T의 모든 순서 없는 잎 쌍 u, v에 대한 경로 길이의 제곱 p2u,v의 합이다. Figure B.1의 유전자 트리 T2에는 여섯 개의 순서 없는 잎 쌍, (Human, Chimpanzee), (Human, Gorilla), (Human, Orangutan), (Chimpanzee, Gorilla), (Chimpanzee, Orangutan), (Gorilla, Orangutan)에 대한 경로가 있다. 경로 길이의 제곱의 합은 22 + 42 + 52 + 42 + 52 + 52 = 111이므로 d(T2) = 111이다.

뿌리 없는 유전자 트리 T가 주어졌을 때, d(T)를 출력하는 프로그램을 작성하라.

프로그램은 표준 입력에서 읽는다. 입력은 정수 n (4 ≤ n ≤ 100,000)을 포함하는 한 줄로 시작하며, n은 입력 유전자 트리 T의 노드 수이다. 그러면 T는 n − 1개의 간선을 가진다. T의 노드는 1부터 n까지 번호가 매겨진다. 다음 n − 1개의 줄은 T의 n − 1개의 간선을 나타내며, 각 줄은 세 개의 음이 아닌 정수 a, b, l (1 ≤ a ≠ b ≤ n, 1 ≤ l ≤ 50)을 포함한다. 여기서 두 노드 a와 b는 계통 길이 l을 가진 간선을 이룬다.

프로그램은 표준 출력에 쓴다. 정확히 한 줄을 출력한다. 그 줄은 하나의 양의 정수 d(T)를 포함해야 한다.