Preparing NOJ

Garden Park

5000ms 1048576K

Description:

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.

Sample Input:

3
1 2 3
2 3 7

Sample Output:

5

Sample Input:

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

Sample Output:

9

Info

CodeForces Gym

Provider CodeForces Gym

Origin 2021 ICPC Asia Taiwan Online Programming Contest

Code GYM103373G

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 10/31/2021 14:46:07

Related

Nothing Yet