Codeforces580C：Kefa与公园的路径选择问题

本文将详细解析Codeforces 580C题目——Kefa与公园。此题涉及图论中的树结构，旨在帮助读者理解如何在特定条件下计算满足条件的路径数量。

Kefa计划用他的第一笔大额薪水庆祝一下，他打算去公园里的餐厅用餐。然而，这个公园并不普通，它是一棵以1号节点为根的树形结构，树中共有n个节点，每个节点可能有也可能没有猫。Kefa的家位于1号节点。不幸的是，Kefa非常害怕猫，因此他不会选择任何一条从餐厅到家的路径中包含超过m个连续有猫的节点的餐厅。

您的任务是帮助Kefa计算他可以选择的餐厅数量。

输入：

第一行包含两个整数n和m（2 ≤ n ≤ 10^5, 1 ≤ m ≤ n），分别表示树的节点数和Kefa能接受的最大连续有猫的节点数。

第二行包含n个整数a_1, a_2, ..., a_n，其中a_i = 0表示第i个节点没有猫，a_i = 1表示第i个节点有猫。

接下来的n-1行描述了树的边，每行包含两个整数x_i和y_i（1 ≤ x_i, y_i ≤ n, x_i ≠ y_i），表示树中的一条边连接了x_i和y_i节点。

输出：

输出一行，包含一个整数——即满足条件的不同叶子节点的数量。

示例：

注释：

在第一个样例中，只有2号节点的餐厅不符合条件，因为从1号节点到2号节点的路径上连续有猫的节点超过了1个。

在第二个样例中，6号和7号节点的餐厅不符合条件，因为从1号节点到这两个节点的路径上连续有猫的节点超过了1个。

解法：

我们可以从根节点开始进行深度优先搜索（DFS），同时维护一个计数器k，用于记录当前路径上连续遇到的有猫的节点数。如果在某条路径上的k超过了m，则停止在这条路径上的进一步探索。最终的答案就是所有能够到达的叶子节点的数量。