Magic Tree
Contest: CEOI 2019 day 2 online mirror (unrated, IOI format)
Tags: *special, data structures, dp, trees

We have a magic tree: a rooted tree on $$$n$$$ vertices. The vertices are numbered $$$1$$$ through $$$n$$$. Vertex $$$1$$$ is the root.

The magic tree gives us magic fruit. The fruit only grows in vertices of the tree other than the root. Each vertex contains at most one piece of fruit.

It is now day 0 and no fruit is ripe yet. Each fruit will only be ripe for a single day. For each fruit, we are given the vertex $$$v_j$$$ where it grows, the day $$$d_j$$$ on which it will be ripe, and the amount $$$w_j$$$ of magic juice we can extract from it if we harvest it when it is ripe.

The fruits have to be harvested by cutting some branches of the tree. On each day, you may cut as many branches of the tree as you like. The parts of the tree you cut off will fall to the ground and you can collect all the ripe fruits they contain. All fruits that fall to the ground when they are not ripe are discarded and no magic juice is collected from them.

Formally, on each day, you may erase some edges of the tree. Whenever you do so, the tree will split into multiple connected components. You then erase all components that do not contain the root and you harvest all ripe fruits those components contained.

Given is a description of the tree together with the locations, ripening days and juiciness of all $$$m$$$ fruits. Calculate the maximum total amount of magic juice we can harvest from the tree.

Input format:
The first line contains three space-separated integers $$$n$$$ ($$$2 \le n \le 100,000$$$), $$$m$$$ ($$$1 \le m \le n-1$$$) and $$$k$$$ ($$$1 \le k \le 100,000$$$) – the number of vertices, the number of fruits, and the maximum day on which a fruit may become ripe.

The following $$$n-1$$$ lines contain the integers $$$p_2, \dots, p_n$$$, one per line. For each $$$i$$$ (from $$$2$$$ to $$$n$$$, inclusive), vertex $$$p_i$$$ ($$$1 \leq p_i \le i-1$$$) is the parent of vertex $$$i$$$.

Each of the last $$$m$$$ lines describes one fruit. The $$$j$$$-th of these lines has the form "$$$v_j\ d_j\ w_j$$$" ($$$2 \le v_j \le n$$$, $$$1 \le d_j \le k$$$, $$$1 \le w_j \le 10^9$$$).

It is guaranteed that no vertex contains more than one fruit (i.e., the values $$$v_j$$$ are distinct).

Output format:
Output a single line with a single integer, the maximum amount of magic juice we can harvest from the tree.

Constraints:
Time limit: 2.0 s
Memory limit: 1024.0 MB

Note:
Scoring:
Subtask 1 (6 points): $$$n, k \leq 20$$$, and $$$w_j = 1$$$ for all $$$j$$$

Subtask 2 (3 points): fruits only grow in the leaves of the tree

Subtask 3 (11 points): $$$p_i = i-1$$$ for each $$$i$$$, and $$$w_j = 1$$$ for all $$$j$$$

Subtask 4 (12 points): $$$k \leq 2$$$

Subtask 5 (16 points): $$$k \leq 20$$$, and $$$w_j = 1$$$ for all $$$j$$$

Subtask 6 (13 points): $$$m \leq 1,000$$$

Subtask 7 (22 points): $$$w_j = 1$$$ for all $$$j$$$

Subtask 8 (17 points): no additional constraints

In the example input, one optimal solution looks as follows:

- On day 4, cut the edge between vertices 4 and 5 and harvest a ripe fruit with 1 unit of magic juice. On the same day, cut the edge between vertices 1 and 2 and harvest 5 units of magic juice from the ripe fruit in vertex 3.
- On day 7, do nothing. (We could harvest the fruit in vertex 4 that just became ripe, but doing so is not optimal.)
- On day 9, cut the edge between vertices 1 and 4. Discard the fruit in vertex 4 that is no longer ripe, and harvest 3 units of magic juice from the ripe fruit in vertex 6. (Alternately, we could achieve the same effect by cutting the edge between vertices 4 and 6.)

Example input:
6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3

Example output:
9

Editorial:
The first couple subtasks are meant as a reward for understanding the problem statement.
In the subtask 1, we can enumerate all subsets of fruit, decide whether this set is valid (i.e. it doesn't contain pair of fruits $$$u$$$, $$$v$$$ such that $$$u$$$ is an ancestor of $$$v$$$ and $$$u$$$ is ripe earlier than $$$v$$$) and output the maximum.
If all fruit is in the leaves, all fruit can be harvested at proper times, so the answer is simply the total juiciness of all fruits.
In subtask 3, the problem formulated on a path is equivalent to finding the longest non-decreasing subsequence in the list of ripening times along the path. Using any $$$\mathcal O(n \log n)$$$ solution gives the answer.
Not very surprisingly, on a tree the task can be solved by a dynamic programming approach by processing the tree upwards from leaves to the root. The scoring rewards different solutions of how information is stored, merged and propagated in the tree.
For the $$$O(n k)$$$ solution one calculates for each vertex $$$u$$$ and number of days $$$i$$$ the following quantity: $$$$$$C_{v, \ell} = \mbox{maximum total juiciness one can harvest from the subtree rooted at $v$ during the first $i$ days.}$$$$$$ The transition for parent $$$u$$$ and children $$$v_i$$$ is $$$$$$C'_{u, \ell} = \sum_{v_i} C_{v_i, \ell}$$$$$$ $$$$$$C_{u, \ell} = \begin{cases} \max( C'_{u, \ell}, w_u + C'_{u, d_u}) & \text{if fruit in $u$ is ripe at $d_u \leq \ell$} \\ C'_{u, \ell} & \text{otherwise} \end{cases}$$$$$$ Obviously the above recurrence can be computed in $$$O(k\cdot \mathrm{\#~children~of~} v)$$$ in a vertex $$$v$$$. As each vertex can be a child of only a single vertex the total time complexity is $$$O(nk)$$$.
This solves subtasks $$$4$$$ and $$$5$$$, and if we also compress the coordinates and the tree, it solves subtask $$$6$$$.
Improving the dynamic programming
We will now do several small steps that will ultimately result in an $$$O(n\log^2 n)$$$ solution.
First of all note that for a fixed vertex $$$u$$$ the values $$$C_{u,i}$$$'s are non-decreasing function of $$$i$$$.
A nontrivial observation is that there are not arbitrarily many distinct values of $$$C_{u,i}$$$'s. In particular, there are at most one more than the number of vertices in the subtree of $$$u$$$, as the steps in this function can occur only at days when a fruit is ripe. We can use this to obtain a sparse representaiton of $$$C_{u,i}$$$ which will be increasing.
For example the following function
If we represent these in a simple array we can do the merge of two sparse representations of the functions using two pointers. This can give us a solution in which we process a vertex $$$u$$$ in time proportional to the size of its subtree – i.e., worst-case $$$O(n^2)$$$.
(Note that another related way to get an $$$O(n^2)$$$ solution when $$$k$$$ is much larger than $$$n$$$ is to do coordinate compression on the times when the fruits become ripe.)
At this point we assume that our tree is a binary tree as arbitrary tree can be always converted into a binary tree. Hence we will only be merging two arrays into one.
In order to do this efficiently we have to represent our sparse function in a different datastructure as we cannot afford to run both pointers on the full range of the larger array. This datastructure is a range tree – one stores the ranges where the function value is constant. To combine two trees, one can iterate over all ranges in one of the trees, and perform a range addition on the second tree. Two trees can thus be combined in $$$O(m \log n)$$$, where $$$m$$$ is the size of the smaller of the trees. Merging a smaller structure into larger one is a well know trick that only adds a logarithmic factor. Furthermore, the act of adding a fruit to a representation can also be done in time $$$O(\log n)$$$ by one lookup and one range addition.
For subtask $$$7$$$, we don't even need a range tree – a simple multiset is enough. In this multiset we store the IDs of days in which a fruit can be harvest from a subtree. Each prefix of this multiset gives us the number of fruits that may be harvested until a particular day, although the set itself is not necessarily correct. Merging subtrees from two siblings is a simple smaller-to-larger merge. To process fruit that is in the root of a subtree, we first remove the earliest fruit that ripes after the fruit in the root, if any, and then add the fruit itself.