P4897 [Template] Gomory-Hu Tree (Minimum Cut Tree)

This is a template problem. Before solving it, please make sure you know Dinic or ISAP. If you brute-force your way through, I will ask you to smoke. By convention, network flow problems do not allow testdata that hacks Dinic/ISAP, but they may hack EK. The testdata for this problem strictly follows the rule above.

Given an undirected connected graph with $n + 1$ vertices and $m$ edges, labeled from $0$ to $n$, answer multiple queries asking for the minimum cut between two vertices. The minimum cut between two vertices is defined as follows: each edge in the original graph has a cost to cut it, and you need to make the two vertices disconnected with the minimum total cost.

The first line contains two integers $n, m$. The next $m$ lines each contain three integers $u, v, w$, indicating an undirected edge between $u$ and $v$, with cutting cost $w$. The next line contains an integer $Q$, the number of queries. The next $Q$ lines each contain two integers $u, v$. You need to compute the minimum cut between $u$ and $v$.

Output $Q$ lines. Each line contains one integer, the answer to the corresponding query.

Constraints: $1 \le n \le 500$, $0 \le m \le 1500$, $0 \le Q \le 10^5$, $0 \le w \le 10^4$, and $u \neq v$. Translated by ChatGPT 5