Problem 1390 --SUSTech Tower Defence
1390: SUSTech Tower DefenceTime Limit: 1 Sec Memory Limit: 128 MB
Submit: 347 Solved: 153
Two players are playing a game named "SUSTech Tower Defence". One player should choose two cities \(a\), \(b\) to defend and then any soldiers cannot go through these two cities. The job of the other player is to choose as many pairs \((u,v)\) as possible so that he/she can go to \(v\) starting from \(u\) without passing the cities \(a\), \(b\).
Here comes a question - how many pairs \((u,v)\) (\(u\le v\)) are there where we cannot go to \(v\) from \(u\) without passing both of the cities \(a\), \(b\)?
Come and help them.
The given graph is an undirected graph.
It is guaranteed that from any city you can pass to any other by roads.
Line 1: Four integers \(n(2\le n\le10^5)\), \(m(n-1\le m\le10^5)\), \(a(1\le a\le n)\) and \(b(1\le b\le n)\), where \(n\)is the number of nodes, \(m\) is the number of undirected edges, \(a\) and \(b\) are two cities to be defended.
There are \(m\) lines following:
Line 2~(m+1): Two integers \(u\) and \(v\), which means there is an undirected edge between \(u\) and \(v\).
One integer represents the answer to the question.
7 7 3 5