NITTROAD - Roads of NITT
The Institute of NITT believes in frugality. So when they made the plan for interconnecting the N hostels, they decided to construct as few bidirectional roads as possible. The hostels are interconnected with roads in such a way that every pair of hostels is connected by exactly one path.
Moreover, they were so frugal that they used low quality tar in making the roads. As a result, the roads start to crack and cannot be used anymore.
Now Alpa has a set of queries. At the time of each query, he knows the roads that are un-usable. He wants to find the number of pairs of hostels that are disconnected, i.e, the number of pairs (x,y) such that 1 <= x < y <= N and there exists no path between hostels x and y.
Help him find the result for each query.
Test cases <= 5
No. of hostels, N <= 20000
No. of queries, Q <= 20000
First line contains t, the total test cases.
Each test case looks as follows:
First line contains N, total number of hostels.
Next N - 1 lines contain two integers x and y, indicating that there is a road between x and y. (1 <= x < y <= N). The roads are numbered from 1 to N - 1.
Next line contains Q, total number of queries.
Next Q lines contain the Q queries.
Each query may be of the following two forms:
R x - Remove the road numbered x. It is guaranteed that this road existsand hasn't already been removed.
Q - Output the total number of pairs (x, y) such that 1 <= x < y <= N and there exists no path between hostels x and y.
For each test case,
Output a line for each query with the required value.
Print a blank line after each test case.
3 1 2 1 3 5 Q R 1 Q R 2 Q 4 1 2 1 3 1 4 7 Q R 1 Q R 2 Q R 3 Q Output: 0 2 3 0 3 5 6
250 comes up with such a nice problem! :))
Can anyone give a hint on how to solve this problem?...
Do all the vertices become disconnected after executing all the queries ?
Think Reverse....a must do problem
Couldn't think of the approach myself. A great question to learn new things. If you can't think of the solution by yourself do take help don't leave this question.
Awesome problem :)
Certainly one of the finest graph problem !
Anyone has an online solution?