ICPC 2019 Asia Regional – Seoul Problem B- Gene Tree > 문제은행 : 정보올림피아드&알고리즘

공지   새로운 정올 베타버전이 공개되었습니다.    자세히보기


4385 : Gene Tree

제한시간
1000 ms   
메모리제한
512 MB   
해결횟수
0 회   
시도횟수
6 회   

문제

A gene tree is a tree showing the evolution of various genes or biological species. A gene tree represents the relatedness of specific genes stored at the leaf nodes without assumption about their ancestry. Leaf nodes represent genes, called taxa, and internal nodes represent putative ancestral taxa. Each edge in the tree is associated with a positive integer, phylogenetic length, which quantifies the evolutionary distance between two nodes of the edge. For example, the left figure below shows a gene tree with six leaf nodes, which approximates the relation among six taxa, and the right one shows a gene tree with four taxa.

 

 


Like the trees T1 and T2 above, gene trees are modeled as unrooted trees where each internal node (non-leaf node) has degree three. A path-length between two leaf nodes is the sum of the phylogenetic lengths of the edges along the unique path between them. In T1, the path-length between Human and Cow is 2 + 3 = 5 and the path-length between Human and Goldfish is 2 + 4 + 8 + 10 = 24. These lengths indicate that Human is much closer to Cow than to Goldfish genetically. From T2, we can guess that the primate closest to Human is Chimpanzee.

 

Researchers are interested in measuring the distance between genes in the tree. A famous distance measure is the sum of squared path-lengths of all unordered leaf pairs. More precisely, such a distance d(T) is defined as follows:

 


where pu,v is a path-length between two leaf nodes u and v in T. Note that d(T) is the sum of the squared path-lengths p2u,v over all unordered leaf pairs u and v in T. For the gene tree T2 in Figure B.1, there are six paths over all unordered leaf pairs, (Human, Chimpanzee), (Human, Gorilla), (Human, Orangutan), (Chimpanzee, Gorilla), (Chimpanzee, Orangutan), and (Gorilla, Orangutan). The sum of squared path-lengths is 22 + 42 + 52 + 42 + 52 + 52 = 111, so d(T2) = 111.

 

Given an unrooted gene tree T, write a program to output d(T).​ 


입력형식

Your program is to read from standard input. The input starts with a line containing an integer n (4 ≤ n ≤ 100,000), where n is the number of nodes of the input gene tree T. Then T has n − 1 edges. The nodes of T are numbered from 1 to n. The following n − 1 lines represent n − 1 edges of T, where each line contains three non-negative integers a, b, and l (1 ≤ a ≠ b ≤ n, 1 ≤ l ≤ 50) where two nodes a and b form an edge with phylogenetic length l. 


출력형식

Your program is to write to standard output. Print exactly one line. The line should contain one positive integer d(T). 


입력 예

복사하기

4
1 4 1
4 3 1
2 4 1

출력 예

복사하기

12

입력 예

복사하기

6
1 5 1
5 2 1
5 6 1
6 4 3
6 3 2

출력 예

복사하기

111

입력 예

복사하기

10
1 2 10
10 2 7
3 2 8
3 9 3
9 8 2
7 9 1
6 4 3
4 5 2
3 4 4

출력 예

복사하기

4709


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP