Vaccine Development
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Marichka and Zenik are prominent scientists. For a very long time, they have been developing a vaccine that will completely defeat the burdock virus.
The burdock virus consists of molecules and bonds between them. The molecules are numbered from 1 to \(n\). Marichka and Zenik found out that the burdock virus molecules form a tree (a connected graph without cycles) rooted at molecule 1.
A molecule is called weak if it is connected to only one other molecule.
The burdock virus is constantly evolving: new weak molecules appear in it, attaching to existing molecules.
Marichka and Zenik ask you to write a program that will speed up the vaccine development.
The program must process two types of queries:
1\(v\) — a new molecule with number \(m + 1\) appears, which is attached to molecule \(v\) (here \(m\) is the number of molecules before executing the query).2\(v\) — find the length of the shortest path (not necessarily simple) that starts at molecule \(v\) and passes through all weak molecules in the subtree of this molecule. The length of the path is the number of edges (bonds) in this path.
Input
The first line contains an integer \(n\) — the initial number of molecules in the burdock virus.
Each of the next \(n-1\) lines contains a pair of integers — \(a_i\) and \(b_i\), which means that there is a bond between the corresponding molecules.
The next line contains an integer \(q\) — the number of queries.
The next \(q\) lines contain
queries, one per line. Each query has the form \(t\) \(v\),
where \(t\) is the query type
(1 or 2), and \(v\) is the molecule number. Such a molecule
is guaranteed to exist at the time of the query.
Output
For each query of the second type, output a line containing an integer — the answer to this query.
Constraints
\(1 \le n \le 2 \cdot 10^5\),
\(1 \le q \le 2 \cdot 10^5\),
there is at least one query of the second type.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 10 1 2 2 3 3 5 3 4 2 6 6 7 1 8 8 9 8 10 5 2 2 2 8 1 8 2 8 2 10 | 8 3 5 0 |
Notes
For the first query, the optimal path is \(2\to3\to4\to3\to5\to3\to2\to6\to7\),
For the second — \(8\to9\to8\to10\).
For the fourth — \(8\to9\to8\to10\to8\to11\).
For the fifth — \(10\).
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
Vaccine Development - Editorial
What is the length of the shortest path that starts at the root of the tree, passes through all its leaves and returns to the root? It is easy to see that such a path goes along every edge exactly twice, so its length is \(2n - 2\), where \(n\) is the number of vertices of the tree.
How does this length change if we do not need to return to the root after visiting the last leaf? Let \(D_v\) be the distance from the root to vertex \(v\) (we also call it the depth of \(v\)). Clearly, ending at a leaf \(x\) saves exactly \(D_x\) edges. So it pays to end our route at the vertex with the largest \(D_v\).
So to answer a query of the second type, we need the number of vertices in the subtree and the depth of the deepest leaf. If there were no queries of the first type, it would be enough to compute these values for all vertices with a depth-first search. What about the queries of the first type? We move from adding vertices to "switching on" vertices. Consider the tree we get after all queries of the first type (we call it the final tree). Now each vertex of this tree is either switched on or not. A query of the first type switches on the corresponding vertex. For a query of the second type, we need the number of switched-on vertices in the subtree and the maximum depth among the switched-on vertices in the subtree.
Build the Euler tour of the final tree: write out all its vertices in the order of a depth-first search. Every subtree corresponds to a contiguous segment of this tour. This turns subtree queries into segment queries. So now we need a data structure that efficiently supports the following operations:
change the value of an element (to switch on a vertex)
find the sum on a segment (to find the number of vertices in a subtree)
find the maximum element on a segment (to find the deepest leaf)
One such structure is a segment tree. It handles each of these queries in logarithmic time.
Total complexity: \(O(n + q \log(n))\).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|