Chongqing Megacity - MarisaOJ: Marisa Online Judge

Chongqing Megacity

Time limit: 1000 ms
Memory limit: 512 MB
_Chongqing is a municipality in China. Along with Beijing, Shanghai, and Tianjin, Chongqing is one of the four largest and most bustling cities in the country. It is a beautiful city with a high level of urbanization and the most unique transportation infrastructure system in the world._ On a special day, Marisa had the opportunity to visit the city of Chongqing. After some sightseeing, Marisa discovered that her area is a tree, consisting of $n$ vertices and $n-1$ edges. Each vertex includes a building with multiple floors and automatic bridges connecting the floors of adjacent buildings. After investigating and asking the locals, Marisa understood how the buildings at adjacent vertices are connected, specifically as follows: - For two buildings $X$ with $x$ floors and $Y$ with $y$ floors at two adjacent vertices, the $x-k$ th floor of building X will be connected to the $y-k$ th floor of building Y (for all $0 \le k \le min(x,y)-1$). It is known that a floor or a series of floors belonging to vertices forming a path and connected by bridges will create a layer of the city (counted from top to bottom). To ensure the city continuously develops, the local government has proposed changes to demolish some old urban layers and build new ones. Initially, they removed all the previous buildings and then started the improvement process (the initial number of floors of every vertex is 0). Curious about the new planning of the area, Marisa found out that there will be $q$ improvements occurring, which belong to one of the following two types: - The first type is in the form $u,v,k$, indicating that the government will build $k$ additional urban layers on the buildings at the vertices along the simple path from $u$ to $v$. - The second type is in the form $u,v,k$, indicating that the government will remove the first $k$ urban layers from the buildings at the vertices along the simple path from $u$ to $v$. If there is no longer a layer connecting all vertices along the path, the removal process stops. Given that the automatic bridges will reconnect the floors after each improvement according to the given rule. Because Marisa wants to learn more about the planning and architecture of the mega-city Chongqing, she wants to know how many vertices have buildings with at least one floor after each improvement. Please help Marisa complete this task! ### Input - The first line contains two positive integers $n$ and $q$. - The next $n-1$ lines, each containing two integers $u,v$ indicating that there is an edge connecting vertex $u$ and $v$. - The next $q$ lines, each containing 4 positive integers $t,u,v,k$ with $t$ indicating the type of improvement, $u,v$ being the related vertices, and $k$ being the number of layers to be improved. ### Output - After each query, print the result which is the number of vertices that satisfy the condition. ### Constraints - $1 \le n, q \le 10^5$. - $1 \le t \le 2$. - $1 \le u, v \le n$. - $0 \le k \le 10^9$. ### Example Input: ``` 5 4 1 2 2 3 3 4 4 5 1 2 4 3 2 2 2 1 2 2 3 3 1 1 4 2 ``` Output: ``` 3 3 2 4 ``` ### Explanation - In the first query, the government builds 3 layers of buildings on vertices 2, 3, and 4. Each of these vertices now has 3 floors, so the number of vertices with at least one floor is 3. - In the second query, the government demolishes the top layer of building 2 (the second floor of building 2 will have a bridge to the third floor of building 3, so the top layer includes the second floor of building 2, the third floor of building 3, and building 4. The lower floors will automatically adjust the bridges to form layers). After that, the number of vertices with at least one floor is 3. - In the third query, the government can only demolish 2 layers instead of 3 as planned because building 2 only has 2 floors left. Now, the building at vertex 2 has 0 floors left, while the building at vertex 3 has 1 floor left. The answer is 2. - In the final query, when all vertices from 1 to 4 are built with two additional top layers, each vertex gains 2 more floors, so there are 4 vertices with buildings having at least one floor.
Topic
Tree
Data structure
Rating 2000
Source MarisaOJ Original
Solution (1) Solution