Do you remember the problem from ICPC Dhaka Regional 2018 named $Path$
$Intersection$
by Md. Imran Bin Azad? This is an extended version of that problem.
You're given an unweighted tree consist of $N$
nodes and $N-1$
edges. Every pair of nodes have a unique simple path between them.
You've to perform $Q$
queries on this tree. There can be three different types of queries. Initially, you've an empty set of paths.
$\texttt{Add A B}$
:
Add a path between node $A$
and $B$
in the set of paths. You'll not be given a path that already exists in the set of paths.
$\texttt{Remove A B}$
:
Here you'll be given a path between node $A$
and $B$
that exists in the set of paths. You've to remove that path from the set of paths.
$\texttt{Answer}$
:
Find the total number of nodes which are part of exactly $K$
paths from the set of paths and the value of $K$
is maximized. If the set is empty, just print 0 0.
The first line of input consists of two integers $N$
and $Q$
$( 3 ≤ N, Q ≤ 10^5)$
number of nodes in the tree and the number of queries to perform respectively.
Each of the next $N-1$
lines consists of two integers $U$
and $V$
$(1 ≤ U,V ≤ N, U\neq V)$
denoting there is an edge between node $U$
and $V$
.
Following next $Q$
lines consists of one of three types of queries in the following format:
$\texttt{Add A B}$
$(1 ≤ A, B ≤ N, A\neq B)$
$\texttt{Remove A B}$
$(1 ≤ A, B ≤ N, A \neq B)$
$\texttt{Answer}$
For each of the $Answer$
type queries, you've to print $X$
and $K$
in one line separated by a single space. The total number of nodes part of $K$
paths from the set of paths and the maximized value $K$
. If the set is empty, just print $0$
$0$
instead.
Input | Output |
---|---|
9 13 1 2 1 3 2 4 2 5 3 6 3 7 4 8 2 9 Answer Add 1 8 Answer Add 5 4 Answer Add 2 9 Answer Add 8 7 Answer Add 4 8 Answer Remove 9 2 Answer | 0 0 4 1 2 2 1 3 1 4 2 4 1 4 |