Nowadays, the Kingdom of Dreamgrid is suffering from a national pandemic. Fortunately, president Baobao is working effectively with the Center for Disease Control (CDC) and they are trying their bes
Nowadays, the Kingdom of Dreamgrid is suffering from a national pandemic. Fortunately, president Baobao is working effectively with the Center for Disease Control (CDC) and they are trying their best to make everything under control. As the chief of CDC, you are required to update the situation simultaneously and answer queries from president Baobao himself and reporters from News agencies in the world. Specifically, let's consider the country as a map of n nodes, denoting cities. Due to the severe pandemic, most roads and highways are closed except n-1 roads, which keep the country connected. We also define F(x) for each city x as the severity of the local disease situation. Now you need to deal with three kinds of events/queries: Another outbreak happens in city x with the severity value of w. For each city y, F(y) will be increased by w−dist(x,y)w-mathit{dist}(x,y)w−dist(x,y), where dist(x,y)mathit{dist}(x,y)dist(x,y) is the number of edges on the path from x to y. Update F(x) of city x to min(F(x),0)min(F(x),0)min(F(x),0), which means the situation in city x has been improved with the effort of the government and medical faculties. Query for the severity value F(x) of city x. Every city's severity value F is 0 initially. Also, F(x) can be negative in some moment and we don't have to adjust it.
