408903: GYM103373 G Garden Park

G. Garden Parktime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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\in\{1,2,\dots,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\neq y$$$, there exists a sequence of trails $$$s_1,s_2,\dots,s_k$$$ satisfying the following conditions.

• Place $$$x$$$ is an end of trail $$$s_1$$$.
• Place $$$y$$$ is an end of trail $$$s_k$$$.
• For $$$1\le 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\in\{1,\dots,k-1\}$$$, then $$$z$$$ cannot be a common end of any other pairs of trails in $$$s_1,\dots,s_k$$$.

In other words, a visitor move from $$$x$$$ to $$$y$$$ by walking along the trails $$$s_1,s_2,\dots,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 $$$\ell(t)$$$, and a visitor can learn $$$\ell(t)$$$ by walking through trail $$$t$$$. A simple path $$$s_1,s_2,\dots,s_k$$$ from $$$x$$$ to $$$y$$$ is with strictly increasing labels if $$$\ell(s_1)<\ell(s_2)<\cdots<\ell(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.

Input

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 $$$\ell(i)$$$ on trail $$$i$$$ is $$$c_i$$$.

• $$$1 \le n \le 2\times 10^5$$$
• $$$1\le a_i\le n$$$ for $$$i\in \{1,2,\dots,n\}$$$.
• $$$1\le b_i\le n$$$ for $$$i\in \{1,2,\dots,n\}$$$.
• $$$0\le c_i\le 10^9$$$ for $$$i\in \{1,2,\dots,n\}$$$.
• $$$a_i\neq b_i$$$ for $$$i\in \{1,2,\dots,n\}$$$.

Output

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

ExamplesInput

3
1 2 3
2 3 7

Output

5

Input

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

Output

9