Masha and Cactus

The whole problem is really this:

You are given some weighted tree paths. Pick a maximum-weight subset of pairwise vertex-disjoint paths.

That’s it. The cactus wording is just the costume.

Observation 1: cactus $\iff$ chosen tree paths are vertex-disjoint

Start with a tree. Adding one extra edge $(u,v)$ creates exactly one cycle: the edge itself plus the unique tree path between $u$ and $v$.

If we choose several extra edges, then a tree vertex belongs to a cycle iff it lies on the corresponding tree path.

So the graph is a cactus iff no tree vertex belongs to two different such cycles, i.e. iff the chosen tree paths are pairwise vertex-disjoint.

So we need the maximum total beauty of a subset of given paths that are pairwise vertex-disjoint.

Observation 2: subtree DP

Root the tree at $1$.

Let:

• $dp[v]$ = maximum beauty obtainable using only vertices in the subtree of $v$.
• $S[v] = \sum\limits_{u \text{ child of } v} dp[u]$.

Now ask: what happens at vertex $v$?

Case 1: $v$ is not used by any chosen path

Then no chosen path can go through $v$, so every chosen path lies completely inside one child subtree. The subtrees are independent, therefore the best value is just

$$S[v].$$

Case 2: $v$ is used by a chosen path

Then exactly one chosen extra edge has a tree path containing $v$. Why exactly one? Because if two chosen paths touch $v$, they are not vertex-disjoint. End of story.

Also, that special edge must satisfy

$$\operatorname{lca}(x,y)=v.$$

So for each node $v$, we only need to consider extra edges whose LCA is $v$.

That’s the big structural simplification.

Observation 3: contribution of a blocked chain

Suppose we decide to choose an extra edge whose path uses the chain from $v$ down to some descendant $t$. All vertices on that chain are now blocked, so we can only take solutions in the side subtrees hanging off the chain.

Define $B_v(t)$ as the maximum beauty obtainable from the side subtrees when every vertex on the path $v \rightsquigarrow t$ is blocked.

If the path is

$$v=x_0, x_1, x_2, \dots, x_k=t,$$

then at each internal node $x_i$ we may keep all child subtrees except the one continuing the blocked chain. So:

$$B_v(t)=\sum_{i=0}^{k-1}\bigl(S[x_i]-dp[x_{i+1}]\bigr)+S[t].$$

Equivalently,

$$B_v(t)=S[t]+\sum_{u\in path(v\to t),\ u\neq v}\bigl(S[parent(u)]-dp[u]\bigr).$$

Observation 4: value of choosing one extra edge with LCA $v$

Take an extra edge $(x,y,c)$ with $\operatorname{lca}(x,y)=v$. If we choose it, then the two blocked branches are $v \rightsquigarrow x$ and $v \rightsquigarrow y$.

Their side contributions are $B_v(x)$ and $B_v(y)$. But the side subtrees of $v$ are counted in both, so subtract $S[v]$ once.

Therefore the value of choosing this edge is

$$c + B_v(x) + B_v(y) - S[v].$$

This even works when one endpoint equals $v$, because then $B_v(v)=S[v]$.

So the DP recurrence is

$$dp[v]=\max\Bigl(S[v],\ \max_{(x,y,c):\operatorname{lca}(x,y)=v}\bigl(c+B_v(x)+B_v(y)-S[v]\bigr)\Bigr).$$

So far, so good. The annoying part is computing all these $B_v(\cdot)$ fast.

Observation 5: turn the path sum into range updates + point queries

Look at the formula

$$B_v(t)-S[t]=\sum_{u\in path(v\to t),\ u\neq v}\bigl(S[parent(u)]-dp[u]\bigr).$$

Define a weight on every non-root node:

$$w(u)=S[parent(u)]-dp[u].$$

Then

$$B_v(t)-S[t]=\sum_{u\in path(v\to t),\ u\neq v} w(u).$$

Now here comes the slick part.

When $S[parent(u)]$ becomes known, we add $w(u)$ to every node in the subtree of $u$. Why? Because for any descendant $t$ of $u$, the path from an ancestor to $t$ includes the edge into $u$.

Using an Euler tour, "add to subtree" becomes a range add on $[tin[u], tout[u]]$. Then a point query at $t$ returns the sum of $w(\cdot)$ over all ancestors $u$ of $t$ whose updates have already been applied.

If we process nodes bottom-up, then while processing a node $v$:

• all descendants of $v$ are already processed,
• all ancestors of $v$ are not processed yet.

So a point query at a descendant $t$ gives exactly the sum of $w(u)$ on the path from $v$ down to $t$. No contamination from above. Beautiful.

Thus while processing $v$,

$$\text{query}(t)=B_v(t)-S[t].$$

Therefore for an extra edge $(x,y,c)$ with $\operatorname{lca}(x,y)=v$,

$$c+B_v(x)+B_v(y)-S[v] = c + \text{query}(x)+S[x] + \text{query}(y)+S[y] - S[v].$$

That is exactly what we evaluate.

Full algorithm

1. Read the rooted tree.
2. Precompute binary lifting tables for LCA.
3. Compute an Euler tour $(tin, tout)$ for subtree intervals.
4. For each extra edge $(u,v,c)$:
   • compute $l=\operatorname{lca}(u,v)$,
   • store the edge in a list attached to node $l$.
5. Process nodes bottom-up.
   • Since the input guarantees $p_i < i$, processing from $n$ down to $1$ is already a valid postorder. Very convenient.
   • Compute $S[v]=\sum dp[child].$
   • For every child $u$ of $v$, add $S[v]-dp[u]$ to the Euler interval of subtree $u$ in a Fenwick tree.
   • Initialize $dp[v]=S[v]$.
   • For each stored extra edge $(x,y,c)$ with LCA $v$, compute $$cand = c + \text{query}(x)+S[x] + \text{query}(y)+S[y] - S[v].$$ Maximize $dp[v]$ with it.
6. Output $dp[1]$.

Why this is correct

We’ll keep it short and sharp.

Lemma 1

For any node $v$, if $v$ is not used by any chosen path, the best value inside subtree $v$ is $S[v]$.

Reason: then every chosen path lies fully inside one child subtree, and child subtrees are independent.

Lemma 2

If $v$ is used, then exactly one chosen extra edge has LCA equal to $v$.

Reason: any chosen path using $v$ has highest vertex $v$, so its endpoints’ LCA is $v$. Two such paths would both contain $v$, violating vertex-disjointness.

Lemma 3

For any descendant $t$ of $v$,

$$B_v(t)=S[t]+\sum_{u\in path(v\to t),\ u\neq v}(S[parent(u)]-dp[u]).$$

Reason: along the blocked chain, each vertex contributes the optimum of all side child-subtrees not continuing the chain.

Lemma 4

While processing node $v$, the Fenwick point query at a descendant $t$ equals $B_v(t)-S[t]$.

Reason: each node $u$ contributes $S[parent(u)]-dp[u]$ to the whole subtree of $u$. A point $t$ receives that value iff $u$ is an ancestor of $t$. Since we process bottom-up, updates from ancestors of $v$ are not applied yet, so only the path below $v$ remains.

Lemma 5

For every extra edge $(x,y,c)$ with $\operatorname{lca}(x,y)=v$, the best value of solutions using that edge is

$$c + \text{query}(x)+S[x] + \text{query}(y)+S[y] - S[v].$$

Reason: by Lemma 4 this is exactly $c+B_v(x)+B_v(y)-S[v]$.

Putting the lemmas together, $dp[v]$ is the maximum of:

• not using $v$: $S[v]$,
• using exactly one extra edge whose LCA is $v$.

So the recurrence is complete and exact. Hence $dp[1]$ is the answer.

Complexity

• LCA preprocessing: $O(n \log n)$
• LCA for all extra edges: $O(m \log n)$
• Fenwick updates/queries: $O((n+m)\log n)$

Total:

$$O((n+m)\log n)$$

Memory:

$$O(n\log n + m).$$

Which is easily fine for $2\cdot 10^5$.

No cursed tree knapsack, no quadratic nonsense, no prayer circle required.