Uplink
Author: 0xIDA
Platform: HTB · Category: coding · Difficulty: insane
Solvers
Summary
A tree DP problem involving minimizing the time to transfer data from each node to the root. Each node can "jump" directly to any ancestor (not just the parent), and each jump cost depends on the source node's transfer speed, preparation time, and the target ancestor's receiving time. This reduces to a convex hull trick (CHT) DP on a tree, requiring a Li Chao segment tree with undo support for DFS rollback.
Challenge
- Network of N computers arranged as a rooted tree (node 1 is root/manager).
- Each node i has: parent p[i], distance to parent d[i], transfer speed t[i], preparation time prep[i], receiving time recv[i].
- A node can send data to ANY ancestor (parent, grandparent, ... , root) in a single "jump".
- Each jump from node i to ancestor j costs:
d(i,j) × t[i] + prep[i] + recv[j]where d(i,j) is the sum of edge distances between i and j. - Goal: For each node 2..N, find the minimum total time to reach root.
Solution Approach
DP Formulation
dp[i] = min over ancestors j of (d(i,j) × t[i] + prep[i] + recv[j] + dp[j])
where dp[1] = 0 (root takes 0 time).
Let depthDist[i] = sum of edge distances from root to node i.
Then d(i,j) = depthDist[i] - depthDist[j].
Substituting:
dp[i] = depthDist[i] × t[i] + prep[i] + min over ancestors j of
(recv[j] + dp[j] - depthDist[j] × t[i])
This is a classic CHT form: for each node i, we need the minimum of lines
y = (-depthDist[j]) × x + (recv[j] + dp[j]) evaluated at x = t[i],
over all ancestors j of i.
Key properties:
- Lines are added in decreasing slope order (−depthDist is strictly decreasing as we DFS down)
- Queries are at arbitrary x values (not monotonic across branches)
- Must support rollback after processing a subtree (ancestors change per DFS branch)
Li Chao Segment Tree with Rollback
A standard Li Chao tree uses a left-endpoint comparison to decide which line stays at a node. This fails when a line is better at the midpoint but worse at the leftmost point — it gets stored in a subtree unreachable from left-branch queries.
The fix: midpoint-based swap. Compare lines at each segment's midpoint rather than its left endpoint. The line that wins at the midpoint stays at the node; the loser is pushed into the child where its slope suggests it may dominate. This ensures every line lives at a node on every query path where it's relevant.
Rollback works by saving the old value of each Li Chao tree node before modifying it, then restoring them in LIFO order.
Complexity
- Li Chao tree: O(log M) per add/query, where M = number of distinct transfer values
- Total: O(N log M) time, O(N log M) memory from undo history
- Handles N up to 10^5+ easily
Verification
Tested successfully against:
- The challenge example (N=6)
- A random 8-node tree (hidden test case from the server)
Flag
HTB{5UCC355FU11Y_RU1N3D_3N3M135_C0MP4N135_R0xIRg}