Dynamic Programming on Trees with Heavy-Light Decomposition and Matrix Multiplication
Weighted Independent Set with Point Updates on a Tree
Consider a rooted tree where every node carries a weight. We must support point-weight modifications and after each change report the maximum-weight independent set of the entire tree. Node count and operation count are up to (10^5), weights are bounded in absolute value by (10^2).
Standard ...
Posted on Tue, 11 Aug 2026 16:21:13 +0000 by verano