CF1059E Split the Tree

You are given a rooted tree on $ n $ vertices, its root is the vertex number $ 1 $ . The $ i $ -th vertex contains a number $ w_i $ . Split it into the minimum possible number of vertical paths in such a way that each path contains no more than $ L $ vertices and the sum of integers $ w_i $ on each path does not exceed $ S $ . Each vertex should belong to exactly one path. A vertical path is a sequence of vertices $ v_1, v_2, \ldots, v_k $ where $ v_i $ ( $ i \ge 2 $ ) is the parent of $ v_{i - 1} $ .

N/A

N/A

In the first sample the tree is split into $ \{1\},\ \{2\},\ \{3\} $ . In the second sample the tree is split into $ \{1,\ 2\},\ \{3\} $ or $ \{1,\ 3\},\ \{2\} $ . In the third sample it is impossible to split the tree.