CF955F Heaps

You're given a tree with $ n $ vertices rooted at $ 1 $ . We say that there's a $ k $ -ary heap of depth $ m $ located at $ u $ if the following holds: - For $ m=1 $ $ u $ itself is a $ k $ -ary heap of depth $ 1 $ . - For $ m>1 $ vertex $ u $ is a $ k $ -ary heap of depth $ m $ if at least $ k $ of its children are $ k $ -ary heaps of depth at least $ m-1 $ . Denote $ dp_{k}(u) $ as maximum depth of $ k $ -ary heap in the subtree of $ u $ (including $ u $ ). Your goal is to compute .

N/A

N/A

Consider sample case one. For $ k>=3 $ all $ dp_{k} $ will be equal to $ 1 $ . For $ k=2 $ $ dp_{k} $ is $ 2 $ if  and $ 1 $ otherwise. For $ k=1 $ $ dp_{k} $ values are $ (3,1,2,1) $ respectively. To sum up, $ 4·1+4·1+2·2+2·1+3+1+2+1=21 $ .