Do you remember the problem from ICPC Dhaka Regional 2018 named by Md. Imran Bin Azad? This is an extended version of that problem.
You're given an unweighted tree consist of nodes and edges. Every pair of nodes have a unique simple path between them.
You've to perform queries on this tree. There can be three different types of queries. Initially, you've an empty set of paths.
Add a path between node and in the set of paths. You'll not be given a path that already exists in the set of paths.
Here you'll be given a path between node and that exists in the set of paths. You've to remove that path from the set of paths.
Find the total number of nodes which are part of exactly paths from the set of paths and the value of is maximized. If the set is empty, just print 0 0.
The first line of input consists of two integers and number of nodes in the tree and the number of queries to perform respectively.
Each of the next lines consists of two integers and denoting there is an edge between node and .
Following next lines consists of one of three types of queries in the following format:
For each of the type queries, you've to print and in one line separated by a single space. The total number of nodes part of paths from the set of paths and the maximized value . If the set is empty, just print instead.
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
Login to submit
This problem can be solved using HeavyHeavyHeavy LightLightLight DecompositionDecompositionDecomposi...