No.1002 Twotone
タグ : / 解いたユーザー数 48
作問者 :
tsutaj
/ テスター :
tempura_pp
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もしくは右上の雲マークをクリックしてアカウントを作成してください。