Flood watch
Hydrologists are watching a flood on a mountain drainage network. The network is n cells, and from each the water drains into one neighbouring cell downstream or leaves the map. The streams do not close into a loop: from any cell the water sooner or later leaves.
Two kinds of messages arrive. A downpour: x units of water fell in cell v, and they are added to the flow of cell v itself and of all the cells downstream, up to the place where the water leaves the map. A question: what is the largest flow on the path along the riverbeds between cells a and b? A path along the riverbeds is a path in the drainage tree: up from one cell to the place where the streams of both meet, and down to the other.
The third test is the drainage network of the mountains above Almaty, computed from the NASA SRTM relief as in the article: 28,341 cells. The fourth is a single river of a hundred thousand cells.
Input
The first line holds n (1 ≤ n ≤ 10⁵). The second holds n numbers p1, …, pn: cell v drains into cell pv, and pv = 0 means that the water from v leaves the map. Then the number of messages q (1 ≤ q ≤ 10⁴) and q lines: 1 v x, a downpour (1 ≤ x ≤ 1000), or 2 a b, a question. In a question the water from a and from b leaves the map through the same cell; a may equal b. Initially the flow of every cell is zero.
Output
For each question, one number: the largest flow among the cells of the path from a to b, including themselves.
Examples
Example 1
7 0 1 2 3 2 5 3 7 1 4 5 1 6 2 2 4 6 1 7 4 2 7 1 2 4 4 2 6 5
7 11 5 2
Example 2
6 0 1 1 0 4 5 6 1 2 3 1 6 7 2 2 3 2 6 4 1 3 1 2 3 2
3 7 4
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A downpour changes the flow on a whole path from a cell to the edge, and a question asks about a whole path between two cells. How many cells are on such a path in a river of a hundred thousand cells, as in the fourth test? And how many messages are there?
2Hint 2
If the tree were a single chain, a segment tree would be enough: add on a stretch, maximum on a stretch. Can any tree be cut into chains so that any path touches only a few of them?
3The idea
Heavy paths. For each cell choose a heavy child, the tributary with the largest catchment, and number the cells with a depth-first walk that goes into the heavy child first. Then each heavy path is a stretch of numbers, and the path between any two cells is cut into O(log n) such stretches: a climb along a light edge more than doubles the subtree size. Over the numbers, a segment tree with addition on a stretch and maximum.
4Walkthrough
A downpour at v is the path from v to the root of its tree: climb by chain heads and on each piece add x on the stretch of numbers from the head to the current cell. A question about the path a–b is the same climb, but each time from the cell whose chain head is deeper; when the heads coincide, the stretch between the numbers of a and b is left. The answer is the largest of the maxima over all the stretches.
The segment tree is conveniently written bottom up, without recursion: each node has the maximum of its stretch including the additions hanging on the node itself, and the hanging addition. Adding on a stretch puts the addition into O(log n) nodes and recomputes their ancestors; before a question the hanging additions on the two paths from the root to the ends of the stretch are pushed down. The drainage tree may be a forest: each cell from which water leaves has its own walk and its own chains.
4+Solution
5Complexity
Preparation is O(n). Each message is O(log n) stretches of numbers at O(log n) each in the segment tree, O(q log² n) in all. On a chain river there is only one stretch.
6Common mistakes
- Cell by cell. A downpour goes through all the cells downstream, a question climbs from both ends. This is
wrong.py: the answers are right, but on a river of a hundred thousand cells each downpour at the source is a hundred thousand steps, and ten thousand messages do not fit in the time. - Recursion. A recursive depth-first walk will crash on the fourth test: the depth of the tree is a hundred thousand.
- Climbing from the wrong cell. You must climb from the cell whose chain head is deeper, not from the deeper cell, otherwise you can overshoot the place where the streams meet.
- The heavy child by depth. If the chain is continued into the deepest tributary rather than the largest, a path can have on the order of √n stretches.