## Tree Paths

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Java 3.0s
Memory limit: 512M

Author:
Problem type

There exists a tree with vertices and bidirectional edges. Each edge connects vertices and and has a length of . A path between two distinct vertices and is valid if is reachable from and the edge lengths on the path from to form a non-decreasing sequence. Note that a path from to is considered the same as a path from to (whether valid or not). Given the number of vertices and edges of a tree, find the number of valid paths.

#### Constraints

All are distinct.

#### Input Specification

The first line contains a single integer , the number of vertices in the tree.

The next lines contain 3 integers , and , representing a bidirectional edge from to of length .

#### Output Specification

Output a single integer, the number of valid paths. Please note that the answer may not fit inside a 32-bit integer.

Note: You do not need to pass all sample cases to earn points on this problem.

#### Sample Input 1

3
1 2 4
1 3 4

#### Sample Output 1

3

#### Explanation for Sample Output 1

The three valid paths are , and . Notice that and are considered the same path.

#### Sample Input 2

5
1 2 7
1 3 2
2 4 9
2 5 5

#### Sample Output 2

9

#### Sample Input 3

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

#### Sample Output 3

30