Author: Andrian Kurniady
You need two dynamic programming states to solve this problem. First, transform the tree into a rooted tree (just choose any random node as the root). Then define a dynamic programming state as f(curr, k, parent): the maximum sum of weight of k disjoint paths rooted at node curr; parent is a boolean flag that determines if there is an incoming path from parent node. To solve this state we need to try any possible combinations to distribute k to curr‘s childs and choose the best one. If there is an incoming path from parent, then curr can has at most one outgoing path. Otherwise, curr can has at most two outgoing paths. To choose the best selection, you need the second dynamic programming state: dp-knapsack.
I’ll let the implementation details to kurniady, just wait for his blog 😀
This problem was solved by 2 teams: Joy (167) and ZSU_Uriel (209).
- Title Page
- Problem A – Anti Brute Force Lock
- Problem B – Bonus Treasure
- Problem C – Panda Land 7: Casino Island
- Problem D – Disjoint Paths
- Problem E – Expert Enough?
- Problem F – Free Parentheses
- Problem G – Greatest K-Palindrome Substring
- Problem H – Hyper-Mod
- Problem I – ICPC Team Strategy
- Problem J – Jollybee Tournament