C. Азын мод

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Петя азын тоонд дуртай. Хүн бүр эерэг утгатай, аравтын орон нь 4 болон 7 агуулаагүй бол азын тоо байна гэдгийг мэднэ. Жишээ нь: 47, 744, 4 тоонууд нь азын тоонууд бол 5, 17, 467 эдгээр нь азын тоо биш юм. Нэгэн өдөр Петя $n$ оройтой модтой таарчээ. Үүнээс гадна тус мод тодорхой жинтэй байв. Өөрөөр хэлбэл ирмэг тус бүр нь эерэг тоогоор илэрхийлэгдсэн жинтэй. Хэрэв жин нь азын тоо байвал тус ирмэг азтай байна гэж үзнэ. $n$ оройтой мод нь $n - 1$ ирмэгтэй чиглэлгүй холбогдсон график гэдгийг анхаараарай.

Петя $i$-аас $j$ хүртэл $(i, j, k)$ гурвалсан орой хэд байж болох талаар бодож байна. Мөн $i$-аас $k$ хүртэл дор хаяж нэг азтай ирмэг байх ёстой (бүх гурван оройнууд нь хос хосоороо ялгаатай). Гурвалсан оройны дугаар нь $(1, 2, 3)$ байх ба энэ нь $(2, 1, 3)$ болон $(1, 3, 2)$ гэсэн гурвалсан оройтоос ялгаатай.

Ийм гурвалсан оройт хэд байгааг олно уу.

Оролт

Эхний мөр нь $n$ ($1 ≤ n ≤ 10^{5}$) гэсэн ганц тоо агуулах ба энэ нь модны оройнуудын тоог илтгэнэ. Дараагийн $n - 1$ мөрүүд нь $u_{i}$ $v_{i}$ $w_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n, 1 ≤ w_{i} ≤ 10^{9}$) гэсэн гурван бүхэл тоо агуулах ба эдгээр нь ирмэг болон түүний жингээр холбогдсон хос оройнуудыг харуулна.

Гаралт

Гаралтын нэг мөрөнд хариуг харуулах нэг тоо хэвлэнэ үү. C++ дахь 64 бит бүхэл тоог унших болох бичихдээ %lld нарийвчлал ашиглахгүйг анхаарна уу. Үүний оронд cout хэсгийг ашиглах нь зүйтэй (мөн %I64d$ ашиглаж болно).

Орчуулсан: Энхгэрэл

Жишээ тэстүүд

Оролт
4
1 2 4
3 1 2
1 4 7
Гаралт
16
Оролт
4
1 2 4
1 3 47
1 4 7447
Гаралт
24

Тэмдэглэл

Эхний жишээнд $16$ гурвалсан орой байна: $(1, 2, 4), (1, 4, 2), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2)$. Хоёр дахь жишээнд бүх гурвалсан орой нь дараах байдлаар тоологдоно: $432 = 24$.

Сэтгэгдлүүдийг ачааллаж байна...