|
|
此文章由 Goodsup 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 Goodsup 所有！转贴必须注明作者、出处和本声明，并保持内容完整
好吧，看看下面这道题如果能在30分钟内在纸上写出最优解，那你可以去美国试试了：
ISRO has shot to global fame after Mangalyaan. They have decided to build hi-tech ground stations throughout the country which can be used either as a control station or as a launch station (but not as both simultaneously). A control station is one which has all controls to the rocket. A launch station is the site from where a rocket is launched. For a successful launch, ISRO has identified that they need 2 control stations and that these 2 control stations should be equidistant from the launch station.
Initially there is only one ground station having index 0, where the headquarters of ISRO is located. Over a period of time, they plan to build more and more ground stations.
They can perform two kinds of operations (for given V):
Type 0: Build a new ground station and construct a one-way road from the ground station having index V to the newly built ground station. In other words, if the index of the newly built ground station is W, then a one way road V->W having length = 1 is constructed. The index of the new ground station will be the smallest positive integer which is not the index of any existing ground station. (Of course, this also helps them to keep track of the number of ground stations they have built so far.)
Type 1: Given a ground station with index V, count how many unordered pairs (P, Q) of ground stations exist such that the ground stations P and Q are both reachable from V (paths from V to P and V to Q exist), and there exists a ground station R (need not be reachable from V), such that distance(P, R) = distance(Q, R), R ≠ P, R ≠ Q and P ≠ Q. Of course, ISRO wants to know this information beforehand since such pairs (P, Q) are possible candidates for control stations, and R is a possible candidate for the launch station.
Adding more explanation
"Given a ground station with index V, count how many unordered pairs (P, Q) of ground stations exist such that the ground stations P and Q are both reachable from V (paths from V to P and V to Q exist), and there exists a ground station R (need not be reachable from V), such that distance(P,R) = distance(Q, R), R ≠ P, R ≠ Q and P ≠ Q."
As this says, there need not be path from R->P or P->R. How ever please use the following as definition of distance.
Distance(X, Y) = Number of roads in the unique path from X to Y, if the given road network were bi-directional.
Please note that, V->P and V->Q should still exist in directed road network.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer M denoting the number of operations.
Each of the next M lines contain 2 integers - type and V.
if type = 0, then perform type 0 operation (for given V).
if type = 1, then perform type 1 operation (for given V).
Output
For each test case, for each query of type 1, you must print the answer to the query on a separate line.
Constraints
1 ≤ T ≤ 5
1 ≤ M ≤ 100000
0 ≤ type ≤ 1
For both type of operations 0 & 1, the given ground station V would have already been built.
Example
Input:
2
4
1 0
0 0
0 1
1 0
6
0 0
0 1
1 0
0 1
0 2
1 1
Output:
0
1
1
2
Explanation
Example case 1:
First operation is of type 1. There is only 1 ground station (with index 0), so number of pairs are 0.
Second operation is of type 0. A new ground station with index 1 is built, and a road from 0->1 (having length 1) is added.
Third operation is of type 0 again. A new ground station with index 2 is built, and a road from 1->2 (having length 1) is added.
Fourth operation is of type 1. There are 3 ground stations now. (0, 2) is the only valid pair as there exists ground station 1 with distance(2, 1) = distance(0, 1) = 1, and both the stations 0 & 2 are reachable from 0.
Example case 2:
There are 2 operations of type 1. For the first one, (0, 2) is the only valid pair, and for the second one, there are 2 valid pairs pairs - (2, 3) and (1, 4). |
|
罗宋汤 (2007-6-9) keke 
楼主:InTheEnd
发表于 2019-11-17 22:05
发表于 2019-11-18 07:31
