题目思路

题目给定的图是一颗树，所以在已知出发节点的时候可以直接dfs或者bfs来遍历整个图，并且由于每个点只能遍历一次，所以dfs或者bfs的遍历过程就是从根节点到叶子节点。然后遍历到每个点时，看一下猫粮够不够，不够的话就不能继续了。每次成功遍历的时候都要记录一下答案

代码

C++

#include <bits/stdc++.h>

介绍

根据群友的描述，这是一场pdd内推的笔试。参加的人数少，但是难度不低

题目内容

小红生活在美丽的华光林，他非常喜欢这里的环境和氛围。在平常的休息时间，他会在家附近散步，欣赏美景，感受大自然的魅力。顺便会投喂经过遇到的小马们，让它们感受到人类的温暖和关爱。这样的生活让他感到非常满足和幸福。已知华光林共有 $N$ 个广场(分别编号 $1$ ~ $N$ ，小红住在 $1$ 号广场)，以及有 $N-1$ 条道路，保证广场两两之间相互连通，且只有唯一一条通路， 且已知第 $i$ 个广场有 $A_i$ 只马。

小红平时散步的时候有以下这些习惯：

1. 任意一个广场不能两次访问
2. 小红的背包只能装下最多$M$份马粮
3. $1$ 份马粮只能投喂 $1$ 只马
4. 若要经过某个广场则要投喂其中所有的马(^. w .^)

小红想知道，应当如何选择路线使得能投喂到最多数量的广场，且需要的马粮数量最少。

输入描述

第一行，两个整数 $N$ 和 $M$ ，分别表示华光林广场的数量，和准备带出门的马粮的份数( $1\le N\le 50,000$ ， $0\le M\le 5,000,000$ )

第二行，共 $N$ 个整数，其中第 $i$ 个整数 $A_i$ 表示第 $i$ 个广场的马的数量。( $0\le A_i \le 100$ )

接下来 $N-1$ 行，每行两个整数 $X$ 和 $Y$ ，表示编号 $X$ 和 $Y$ 的广场之间存在一条道路。( $1\le X,Y\le N$ )

输出描述

共一行，两个整数，分别表示：能投喂最多数量的广场，以及在此情况下需要最少多少马粮。

样例

样例一：

输入

2 1
2 1
1 2

输出

0 0

样例解释

小红只有 $1$ 份马粮，小于 $1$ 号广场的马马数量，因此小红决定不出门喂马。(T V T)

没有任何一个广场的马咪被投喂，也就不需要任何马粮。

样例二：

输入

3 4
1 2 3
1 2
2 3

输出

2 3