题目描述
Problem Description
Given a directed graph with $n$ vertices and $2m$ edges, each edge is marked with either a left or right parenthesis. There are $k$ different types of parentheses, meaning there are $2k$ different marks in the graph. Vertices, edges, and types of parentheses are all numbered starting from 1.
Each edge in the graph appears in pairs. Specifically, if there exists an edge $(u, v)$ marked with the left parenthesis of the $w$-th type, then there must exist an edge $(v, u)$ marked with the right parenthesis of the $w$-th type. Similarly, each edge marked with a right parenthesis corresponds to an edge in the opposite direction marked with the same type of left parenthesis.
Your task is to determine how many pairs of vertices $(x, y)$ ($1 \le x < y \le n$) exist such that there is a path from $x$ to $y$ in the graph, and the sequence of marks on the edges along this path, when concatenated in order, forms a valid parenthesis sequence.
Input Format
The first line contains three integers $n$, $m$, and $k$, representing the number of vertices, the number of edge pairs, and the number of types of parentheses, respectively.
The next $m$ lines each contain three integers $u$, $v$, and $w$, indicating a directed edge from $u$ to $v$ marked with the left parenthesis of the $w$-th type, and a directed edge from $v$ to $u$ marked with the right parenthesis of the $w$-th type.
In the input graph, multiple directed edges can connect any two distinct vertices, but there are no self-loops, i.e., $u \ne v$.
Output Format
Output a single integer on one line, representing the number of pairs of vertices that satisfy the condition.
Sample Input and Output
Input Sample #1
4 5 1
4 3 1
4 1 1
4 2 1
1 3 1
2 1 1
Output Sample #1
3
Input Sample #2
6 8 2
6 1 2
3 5 1
1 2 2
5 1 2
3 6 2
4 3 1
6 2 2
3 2 1
Output Sample #2
10
Input Sample #3
See attached file bracket/bracket3.in
Output Sample #3
See attached file bracket/bracket3.ans
Input Sample #4
See attached file bracket/bracket4.in
Output Sample #4
See attached file bracket/bracket4.ans
Notes/Hints
[Sample Explanation #1]
The pairs of vertices and their corresponding paths that meet the criteria are:
$(1, 2)$: $1 \to 3 \to 4 \to 1 \to 2$.
$(1, 4)$: $1 \to 3 \to 4$.
$(2, 4)$: $2 \to 1 \to 4$.
[Data Range]
For all test cases: $1 \le n \le 3 \times 10^5$, $1 \le m \le 6 \times 10^5$, $1 \le k, u, v \le n$, $1 \le w \le k$.
Specific constraints for each test case are as follows:
| Test Case Number | $n =$ | $m \le$ | $k \le$ | Special Restrictions |
|---|---|---|---|---|
| $1 \sim 4$ | $4$ | $5$ | $2$ | None |
| $5 \sim 8$ | $8$ | $10$ | $2$ | None |
| $9 \sim 12$ | $3000$ | $6000$ | $1$ | None |
| $13 \sim 16$ | $3000$ | $n - 1$ | $n$ | No cycles consisting only of edges marked with left parentheses |
| $17 \sim 20$ | $3 \times 10^5$ | $n - 1$ | $n$ | No cycles consisting only of edges marked with left parentheses |
| $21 \sim 25$ | $3 \times 10^5$ | $6 \times 10^5$ | $n$ | None |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分