問題一覧 > 通常問題

No.1002 Twotone

レベル : / AI推定難易度 : 2350 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 48
作問者 : tsutaj / テスター : tempura_pp
お気に入りにしたユーザー ProblemId : 3961 / 自分の提出
問題文最終更新日: 2020-02-27 22:21:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 239 (順位表) の他の問題:

Problem Statement

There is an undirected tree with $N$ vertices and $N-1$ edges. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$. The $i$-th edge connects vertices $u_i$ and $v_i$ bidirectionally. Each edge is also colored. There are $K$ colors in total, and the $i$-th edge has color $c_i$.

Find the number of paths $(p, q)$ (where $p < q$) in this tree such that the edges contained in the path have exactly $2$ distinct colors. Here, the edges contained in the path $(p, q)$ refer to the set of edges traversed when going from vertex $p$ to vertex $q$ along the shortest route.

Input

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

Line $1$ gives the number of vertices $N$ of the tree and the number of colors $K$.

The following $N-1$ lines, starting from line $2$, give the information on the edges of the tree. Line $1+i$ $(1 \leq i \leq N - 1)$ indicates that the $i$-th edge connects vertices $u_i$ and $v_i$ bidirectionally and that the color of the edge is $c_i$.

Constraints

  • All inputs are integers
  • $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)$
  • The given graph is guaranteed to be a tree

Output

Print the answer in $1$ line.

Sample

Sample 1
Input
5 5
1 2 3
1 3 1
2 4 5
3 5 1
Output
3

The following $3$ paths satisfy the condition.

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

Note that since we count the total number of paths that use exactly $2$ distinct colors, paths that use only $1$ color and the like are not counted.

Sample 2
Input
8 149146
4 2 42027
2 5 83386
2 6 47328
3 6 37766
7 2 130178
7 1 9283
8 2 48943
Output
12

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