Kefa and Park Problem

Kefa and Park Problem — ExecCode Medium DSA Practice

Solve the Kefa and Park problem on ExecCode. Free online medium DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

The park is a tree of vertices numbered from 1 to n, rooted at 1. cats[i] is 1 when vertex i + 1 contains a cat and 0 otherwise. Kefa walks from the root and refuses to enter a vertex when the path from the root would contain more than m consecutive cats. Return how many leaves he can reach. A leaf is a vertex with no child. The root counts only when it is the only vertex. You are given: edges — undirected tree edges cats — 1 if that vertex has a cat, in vertex order m — the maximum allowed consecutive cats Return the number of reachable leaves. A vertex with no cat resets the consecutive-cat count to 0. Do not continue past a vertex that makes the streak larger than m.

Examples

Input {'edges': [[1, 2], [1, 3], [1, 4]], 'cats': [1, 1, 0, 0], 'm': 1}; Output 2. Input {'edges': [[1, 2]], 'cats': [1, 0], 'm': 0}; Output 0. Input {'edges': [], 'cats': [0], 'm': 0}; Output 1

Constraints

1 <= cats.length <= 100000 edges.length == cats.length - 1 The edges form a tree on vertices 1..n 0 <= m <= n cats[i] is 0 or 1

Practice Kefa and Park free on ExecCode. Browse DSA problems, topic map, and placement guides.