23340번 - Garden Park 다국어

In the Garden park, there are n places of interest (numbered from 1 to n) and n − 1 trails (numbered from 1 to n − 1) connecting the places of interest. For every i ∈ {1, 2, ..., n − 1}, trail i has two ends at place a_i and place b_i, and the trail does not pass any place of interest except its ends. Moreover, the trails do not have any intersection except the ends.

To protect the garden, visitors may only walk along the trails (in any direction) and inside the places of interest. For any pair of places of interest (x, y) where x ≠ y, there exists a sequence of trails s₁, s₂, ..., s_k satisfying the following conditions.

• Place x is an end of trail s₁.
• Place y is an end of trail s_k.
• For 1 ≤ i < k, trail s_i and trail s_i+1 have a common end.
• If place z is the common end of trails s_i and s_i+1 for some i ∈ {1, ..., k − 1}, then z cannot be a common end of any other pairs of trails in s₁, ..., s_k.

In other words, a visitor move from x to y by walking along the trails s₁, ..., s_k without visiting a place of interest twice. Such a sequence is called a simple path from x to y. The administration division of the park plans to host an event in the park. It puts labels on the trails. For trail t, the label on t is an integer ℓ(t), and a visitor can learn ℓ(t) by walking through trail t. A simple path s₁, ..., s_k from x to y is with strictly increasing labels if ℓ(s₁) < ℓ(s₂) < ··· < ℓ(s_k). By reporting m distinct simple paths with strictly increasing labels to the administration division, a visitor may win m free tickets for future visits.

Your friend George just visited the park, and learned all labels on the trails. He wants to win free tickets for future visits with you. Please write a program to compute the number of distinct simple paths with strictly increasing labels in the garden park.

The first line contains one integers n. The (i + 1)-th line contains three integers a_i, b_i, c_i. Trail i connects place a_i and b_i, and the label ℓ(i) on trail i is c_i.

Output the number of distinct simple paths with strictly increasing labels in the garden park.

• 1 ≤ n ≤ 2 × 10⁵
• 1 ≤ a_i ≤ n for i ∈ {1, 2, ..., n}.
• 1 ≤ b_i ≤ n for i ∈ {1, 2, ..., n}.
• 0 ≤ c_i ≤ 10⁹ for i ∈ {1, 2, ..., n}.
• a_i ≠ b_i for i ∈ {1, 2, ..., n}.