题目描述

在花园公园里，有 $n$ 个景点（编号为 $1$ 到 $n$）和 $n-1$ 条小径（编号为 $1$ 到 $n-1$）连接这些景点。对于每个 $i \in \{1, 2, \dots, n-1\}$，小径 $i$ 的两端分别位于景点 $a_i$ 和 $b_i$，且该小径除了端点外不经过任何其他景点。此外，这些小径之间除了端点外没有其他交点。

为了保护花园，游客只能沿着小径（任意方向）行走，并可以在景点内停留。对于任意一对景点 $(x, y)$（$x \neq y$），存在一条小径序列 $s_1, s_2, \dots, s_k$ 满足以下条件：

• 景点 $x$ 是小径 $s_1$ 的一个端点。
• 景点 $y$ 是小径 $s_k$ 的一个端点。
• 对于 $1 \leq i < k$，小径 $s_i$ 和 $s_{i+1}$ 共享一个公共端点。
• 如果景点 $z$ 是某对 $s_i$ 和 $s_{i+1}$（$i \in \{1, \dots, k-1\}$）的公共端点，那么 $z$ 不能是 $s_1, \dots, s_k$ 中任何其他小径对的公共端点。

换句话说，游客从 $x$ 移动到 $y$ 时，沿着小径 $s_1, s_2, \dots, s_k$ 行走，且不会重复经过任何一个景点。这样的序列称为从 $x$ 到 $y$ 的 简单路径。

公园的管理部门计划在园内举办一场活动。他们在小径上贴上标签。对于小径 $t$，其上的标签为整数 $\ell(t)$，游客通过行走经过小径 $t$ 即可获知 $\ell(t)$。一条从 $x$ 到 $y$ 的简单路径 $s_1, s_2, \dots, s_k$ 被称为 严格递增标签路径，如果 $\ell(s_1) < \ell(s_2) < \cdots < \ell(s_k)$。游客向管理部门报告 $m$ 条不同的严格递增标签简单路径，即可赢得 $m$ 张未来参观的免费门票。

你的朋友乔治刚刚参观完公园，并获知了所有小径上的标签。他想和你一起赢得免费门票。请编写一个程序，计算花园公园中严格递增标签简单路径的数量。

输入格式

第一行包含一个整数 $n$。第 $(i+1)$ 行包含三个整数 $a_i, b_i, c_i$。小径 $i$ 连接景点 $a_i$ 和 $b_i$，且小径 $i$ 上的标签 $\ell(i)$ 为 $c_i$。

输出格式

输出花园公园中严格递增标签简单路径的数量。

3
1 2 3
2 3 7

5

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

9

提示

• $1 \leq n \leq 2 \times 10^5$
• $1 \leq a_i \leq n$，对于 $i \in \{1, 2, \dots, n\}$
• $1 \leq b_i \leq n$，对于 $i \in \{1, 2, \dots, n\}$
• $0 \leq c_i \leq 10^9$，对于 $i \in \{1, 2, \dots, n\}$
• $a_i \neq b_i$，对于 $i \in \{1, 2, \dots, n\}$

翻译由 DeepSeek V3.2 完成