問題一覧 > 通常問題

No.1002 Twotone

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 43
作問者 : tsutajtsutaj / テスター : tempura_pptempura_pp
7 ProblemId : 3961 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-02-27 22:21:29

問題文

$N$ 頂点 $N-1$ 辺の無向木があります。頂点は $1$ から $N$ までで、辺は $1$ から $N-1$ まででそれぞれ番号付けられており、$i$ 番目の辺は頂点 $u_i$ と $v_i$ を双方向に結んでいます。また、それぞれの辺には色がついています。色は全部で $K$ 色存在し、$i$ 番目の辺には色 $c_i$ が付いています。

この木のパス $(p, q)$ (ただし $p < q$) であって、パスに含まれる辺の色が ちょうど $2$ 種類 であるものの個数を求めてください。なお、パス $(p, q)$ に含まれる辺とは、頂点 $p$ から頂点 $q$ まで最短経路で向かう際に通過する辺の集合を指します。

入力

$N$ $K$
$u_1$ $v_1$ $c_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$ $c_{N-1}$

$1$ 行目では、木の頂点数 $N$ と色の種類数 $K$ が与えられます。

$2$ 行目以降 $N-1$ 行は、木の辺の情報が与えられます。$1+i$ 行目 $(1 \leq i \leq N - 1)$ は、$i$ 番目の辺が頂点 $u_i$ と頂点 $v_i$ を双方向に接続しており、辺の色が $c_i$ であることを表します。

制約

  • 入力は全て整数で与えられる
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq K \leq 2 \times 10^5$
  • $1 \leq u_i, v_i \leq N$ $(1 \leq i \leq N-1)$
  • $1 \leq c_i \leq K$ $(1 \leq i \leq N-1)$
  • 与えられるグラフは木であることが保証される

出力

答えを $1$ 行で出力してください。

サンプル

サンプル 1
入力
5 5
1 2 3
1 3 1
2 4 5
3 5 1
出力
3

以下の $3$ つのパスが条件を満たします。

  • $(1, 4)$
  • $(2, 3)$
  • $(2, 5)$

ちょうど $2$ 種類の色を使用するパスの総数を数えるため、$1$ 種類のみの色を使用するパスなどは数えないことに注意します。

サンプル 2
入力
8 149146
4 2 42027
2 5 83386
2 6 47328
3 6 37766
7 2 130178
7 1 9283
8 2 48943
出力
12

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。