2
There are two ways this problem can be solved. I really like these solutions.
Square Root Decomposition
Keep a set of at most O(sqrtN) "active nodes".
When you have a query of type 2, just loop through all these active nodes and add the distance between each one to the queried node. When you have a query of type 1, add the new node to the set if ...
1
Yes, the greedy algorithm (you described) works.
Given a directed graph, call a subset of its vertices "a 3-separated set" if there isn't a path of length less than 3 between any pair of vertices among them. Call a 3-separated set a 3-separated-max set if it contains the maximum number of vertices. The problem is to find a 3-separated-max set in a ...
1
You want to prove a false statement.
Its possible that T -{a} + {b} is not spanning tree.
Consider the below example
Lets say T1 is-
1
/ \
2 3
/ /
5 4
/
6
Lets say T2 is-
1
\
2 3
/|\ /
5 6 4
both are spanning tree but if we replace edge 1-2 in T1 with edge 2-6 in T2 then it will not be ...
Only top voted, non community-wiki answers of a minimum length are eligible