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 unusable. 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.
Constraints
Test cases <= 5.
Number of hostels, N <= 20000.
Number of queries, Q <= 20000.
Input
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 exists and 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.
Output
For each test case,
Output a line for each query with the required value.
Print a blank line after each test case.
Example
Input: 2 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
hide comments
nsitsk:
2016-10-12 19:00:45
Awesome problem :)
|
|
Anant Upadhyay:
2016-08-29 17:16:11
Certainly one of the finest graph problem ! |
|
sbansalcs:
2016-08-09 08:26:03
Anyone has an online solution? |
|
hodobox:
2016-07-24 01:54:34
Enjoyed :) |
|
ASHUTOSH DWIVEDI:
2016-06-21 23:45:25
'Kudos' to the problem setter :) |
|
shikhar0037:
2016-05-21 13:07:02
One of the finest graph problem . AC in 1 go :) |
|
torque:
2015-12-30 13:00:33
Great problem!! |
|
free mind ;):
2015-09-12 11:10:22
#15115856 can you look into this solution . can you give me test case , where my solution is failing. please |
|
Rishav Goyal:
2015-07-12 21:14:47
Cool problem |
|
Aayush Agarwal:
2014-05-28 00:18:52
Awesome problem ! |
Added by: | Aditya |
Date: | 2013-02-22 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | That would be me. |