Freaks City

Subtree Budget Allocation and Optimal Path Reconstruction The core challenge revolves around allocating a fixed budget across a binary tree structure to maximize a specific threshold value. The solution begins by analyzing the root's contribution and propagating constraints downward. We define a dynamic programming state dp_max[u][b] representi ...

Re-rooting DP is a tree-DP variant that looks intimidating at first, yet becomes very mechenical once the pattern is recognized. The following problems illustrate the key techniques. Problem 1 – USACO 2012 FEB "Nearby Cows" Task: for every node i compute the sum of weights of all nodes whose distance to i is at most K. Constraints: n ...

We are given a tree of (n) nodes, each carrying an integer weight (which may be negative). The task is to select a connected subgraph that forms a subtree and maximise the sum of the node weights inside it. The problem appears with two common variants: one that allows an empty selection (answer at least 0) and one that requires at least one nod ...

Introduction This is a challenging problem that combines segment tree merging with dynamic programming optimization. While it follows a relatively standard template, the overall difficulty level is high. Prerequisites: Dynamic programming, tree-based DP, segmant tree with dynamic node allocation, segment tree merging. Problem link: Click here D ...

Shortest Path DAG and Convex Hull Optimization This problem involves processing a transportation network where we need to compute both the shortest travel time and the maximum possible delay while still arriving on time. Solution Approach First, we construct the shortest path DAG by running Dijkstra's algorithm from the source node. Any edge no ...

Tree-Based Resource Distribution When distributing a fixed quantity of resources across a tree structure where each node must eventually hold an equal amount, removing any edge partitions the graph into two independent substructures. Let the total resource sum be $S$ and the number of nodes be $N$. The target allocation per node is $k = S / N$. ...

DP optimization often feels like an arcane art. The question arises: can anyone actually devise such solutions during a programming contest? (Perhaps I'm still learning this skill.) The core ideas I've encountered fall into these categories: When transitioning from state i to i+1, the number of states that change is small, so we can inherit val ...