# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Path Intersection Extended

By Peregrine_Falcon · Limits 1s, 256 MB

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.

## Input

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}$

## Output

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.

## Sample

InputOutput
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


• ### Statistics

100% Solution Ratio

BigBagEarliest, 3w ago

serotoninFastest, 0.3s

serotoninLightest, 20 MB

serotoninShortest, 2309B

Login to submit

### Editorial

This problem can be solved using HeavyHeavyHeavy LightLightLight DecompositionDecompositionDecomposi...

### Related Contests

 Criterion 2021 Round 11Ended 3w ago 