정원 공원

정원 공원에는 n개의 명소(1번부터 n번)와 명소를 잇는 n − 1개의 산책로(1번부터 n − 1번)가 있다. 각 i ∈ {1, 2, ..., n − 1}에 대해 산책로 i의 양 끝은 명소 ai와 명소 bi이며, 산책로는 양 끝을 제외하고는 어떤 명소도 지나지 않는다. 또한 산책로끼리는 끝을 제외하고 만나지 않는다.

정원을 보호하기 위해 방문객은 산책로를 따라서만(양쪽 방향 모두 가능) 걸을 수 있고, 명소 안에서만 머물 수 있다. x ≠ y인 임의의 명소 쌍 (x, y)에 대해 다음 조건을 만족하는 산책로 열 s1, s2, ..., sk가 존재한다.

• 명소 x는 산책로 s1의 끝이다.
• 명소 y는 산책로 sk의 끝이다.
• 1 ≤ i < k인 i에 대해 산책로 si와 산책로 si+1은 공통된 끝을 가진다.
• 어떤 i ∈ {1, ..., k − 1}에 대해 명소 z가 산책로 si와 si+1의 공통된 끝이라면, z는 s1, ..., sk 중 다른 어떤 두 산책로의 공통된 끝도 될 수 없다.

다시 말해, 방문객은 명소를 두 번 방문하지 않고 산책로 s1, ..., sk를 따라 x에서 y로 이동할 수 있다. 이러한 열을 x에서 y로 가는 단순 경로라고 부른다. 공원 관리 부서는 공원에서 행사를 열 계획이다. 관리 부서는 산책로에 표지를 붙인다. 산책로 t에 붙는 표지는 정수 ℓ(t)이고, 방문객은 산책로 t를 걸어서 ℓ(t)를 알 수 있다. x에서 y로 가는 단순 경로 s1, ..., sk가 엄격히 증가하는 표지를 가진다는 것은 ℓ(s1) < ℓ(s2) < ··· < ℓ(sk)라는 뜻이다. 엄격히 증가하는 표지를 가진 서로 다른 단순 경로 m개를 관리 부서에 보고하면, 방문객은 앞으로의 방문에 쓸 무료 입장권 m장을 받을 수 있다.

여러분의 친구 George는 방금 공원을 방문했고, 모든 산책로의 표지를 알아냈다. 그는 여러분과 함께 무료 입장권을 받고 싶어 한다. 정원 공원에서 엄격히 증가하는 표지를 가진 서로 다른 단순 경로의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 정수 n이 주어진다. (i + 1)번째 줄에는 세 정수 ai, bi, ci가 주어진다. 산책로 i는 명소 ai와 bi를 잇고, 산책로 i의 표지 ℓ(i)는 ci이다.

정원 공원에서 엄격히 증가하는 표지를 가진 서로 다른 단순 경로의 수를 출력한다.

• 1 ≤ n ≤ 2 × 105
• i ∈ {1, 2, ..., n}에 대해 1 ≤ ai ≤ n.
• i ∈ {1, 2, ..., n}에 대해 1 ≤ bi ≤ n.
• i ∈ {1, 2, ..., n}에 대해 0 ≤ ci ≤ 109.
• i ∈ {1, 2, ..., n}에 대해 ai ≠ bi.