P12849 [蓝桥杯 2025 国 A] 公路

小蓝居住的国家有 $n$ 座城市，城市与城市之间由 $n-1$ 条公路连接，而且任意两个城市都可以通过公路互相到达。 这个国家的公路由几个公司共同修建，如果小蓝希望通过某条公路，就必须持有修建这条公路的公司的通行证，但只要申请一次通行证，就可以在每一条这个公司修建的公路上通行。 小蓝经常要在不同城市之间旅行，每次他要从一个城市到另一个不同的城市，都需要根据需要通过的公路申请相应的通行证。具体来说，如果小蓝的路线经过了一条或者更多条 A 公司修建的公路，小蓝就需要申请一次 A 公司的通行证。 现在小蓝希望知道，对于这 $n \times (n-1)$ 种不同的情况，他需要申请通行证的次数总共是多少。

输入的第一行包含一个正整数 $n$。 接下来 $n-1$ 行，每行包含三个正整数 $u_i, v_i, w_i$，相邻整数之间使用一个空格分隔，表示城市 $u_i$ 和城市 $v_i$ 之间有一条由公司 $w_i$ 修建的公路。

输出一行包含一个整数表示答案。

**【样例说明】** 下表给出了每种情况需要申请的通行证数量，总和为 16。 | | 1 | 2 | 3 | 4 | | --- | --- | --- | --- | --- | | 1 | / | 1 | 1 | 1 | | 2 | 1 | / | 1 | 2 | | 3 | 1 | 1 | / | 2 | | 4 | 1 | 2 | 2 | / | **【评测用例规模与约定】** 对于 30% 的评测用例，$1 \leq n \leq 300$； 对于另外 20% 的评测用例，$u_i = i$，$v_i = i + 1$； 对于另外 20% 的评测用例，$u_i = 1$，$v_i = i + 1$； 对于 80% 的评测用例，$1 \leq n \leq 50000$； 对于所有评测用例，$1 \leq w_i, u_i, v_i \leq n \leq 500000$。