题目思路

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

代码

C++

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 5;
typedef pair<int, int>pii;
int n, m;
int arr[MAXN];
int vis[MAXN];
vector<int>edge[MAXN];
int maxn = 0;
int minn = (int)1e9;
struct Node
{
	int id;//点的id
	int num;//到这个点之后还剩下多少猫粮
	int dis;//走了几个街区了
};
int main(){
	scanf("%d%d", &n, &m);
	memset(vis, 0, sizeof vis);
	for(int i = 1; i <= n; i++)cin >> arr[i];
	for(int i = 1; i <= n - 1; i++){
		int u, v;
		scanf("%d%d",&u, &v);
		edge[u].push_back(v);
		edge[v].push_back(u);//建图
	}
	if(arr[1] > m){
		cout << "0 0" << endl;//如果起点都喂不了，那输出00
		return 0;
	}
	queue<Node>q;//bfs
	q.push({1,m-arr[1],1});//初始在点1，还剩m-arr[1]猫粮,走了1个街区
	vis[1] = 1;//表示点1已经访问过了
	while(!q.empty()){
		Node now = q.front();
		q.pop();
		int u = now.id;
		for(int i = 0; i < edge[u].size(); i++){//遍历邻接点
			int v = edge[u][i];
			if(vis[v])continue;//如果访问过了，就跳过
			int d = now.dis + 1;//街区+1
			int num = now.num - arr[v];//猫粮减少
			if(num >= 0){//如果猫粮够的话
				if(d > maxn){//记录最大街区以及对应的最少猫粮
					maxn = d;
					minn = m - num;
				}else if(d == maxn){//街区数一样，猫粮数最少
					minn = min(m - num, minn);
				}
				vis[v] = 1;//表示访问过了
				q.push({v,num,d});//入队列
			}
		}
	}
	cout << maxn <<" " << minn << endl;
}

python

# ----------FASTIOSTART-----------#

import sys
import os
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


# ----------FASTIOFinished-----------#

def I(): return input()


def II(): return int(input())


def MI(): return map(int, input().split())


def LI(): return list(input().split())


def LII(): return list(map(int, input().split()))
from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc


# sys.setrecursionlimit(100000) #设置递归深度，其中100000是你需要设置的新的递归次数。
# import random
# from graphlib import TopologicalSorter 拓扑排序的包，但是注意这建边的时候，需要反着来 list(TopologicalSorter(g).static_order())
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
# 使用lru_cache装饰器的时候，一定记得传入参数,@lru_cache(None),表示传入的参数正无穷
from heapq import nsmallest, nlargest, heapify, heappop, heappush
# from math import gcd
import math
from bisect import bisect_left, bisect_right
inf = float("inf")
# mod = int(1e9+7)
import timeit

# ------------------------------UserCodeStart-------------------------------#
def solve():
    n, m = MI()
    A = [0]+LII()
    g = defaultdict(list)
    for i in range(n-1):
        x, y = MI()
        g[x].append(y)
        g[y].append(x)
    if A[1] > m:
        print(0, 0)
        return
    vis = set()
    vis.add(1)
    ans1, ans2 = 1, m-A[0]

    def dfs(node, k, tot):
        for nxt in g[node]:
            if nxt in vis: continue
            # dfs遍历，每次遇到一个结点，都更新一下数据
            d = k + 1
            num = tot-A[nxt]
            nonlocal ans1, ans2
            if num >= 0:
                if d > ans1:
                    ans1 = d
                    ans2 = m-num
                elif d == ans1:
                    ans2 = min(ans2, m-num)
                vis.add(nxt)
                dfs(nxt, k+1, tot-A[nxt])

    dfs(1, 1, m-A[1])
    print(ans1, ans2)

def main():
    T = 1
    for _ in range(T):
        solve()
# -------------------------------UserCodeFinish-------------------------------#
if __name__ == "__main__":
    main()

java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
    static int[] a;
    static HashMap<Integer, ArrayList<Integer>> b = new HashMap<Integer, ArrayList<Integer>>();
    static boolean[] vis;
    static int m;
    static int n;
    static int min_m;
    static int max_n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        a = new int[n + 1];
        vis = new boolean[n + 1];
        for (int i = 0; i < n; i++) {
            a[i + 1] = scanner.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            ArrayList<Integer> integers = b.computeIfAbsent(x, t -> new ArrayList<Integer>());
            integers.add(y);
            b.put(x, integers);
            ArrayList<Integer> integers1 = b.computeIfAbsent(y, t -> new ArrayList<Integer>());
            integers1.add(x);
            b.put(y, integers1);
        }
        if (m < a[1]) {
            System.out.println(0 + " " + 0);
            return;
        }
        ArrayList<Integer> list = b.get(1);
        vis[1] = true;
        backtrack(list, a[1], 1);
        System.out.println(max_n + " " + min_m);
    }

    static void backtrack(ArrayList<Integer> list, int total_m, int total_n) {
        if (list == null) return;
        if (total_m>m) return;

        if (total_n == max_n && total_m < min_m) {
            min_m = total_m;
        }
        if (total_n == n) {
            max_n = n;
            min_m = total_m;
            return;
        }
        if (total_n > max_n) {
            max_n = total_n;
            min_m = total_m;
        }

        for (int e : list) {
            if (vis[e]) continue;
            vis[e] = true;
            total_m += a[e];
            total_n++;
            backtrack(b.get(e), total_m, total_n);
            total_m -= a[e];
            total_n--;
            vis[e] = false;
        }
    }
}

介绍

根据群友的描述，这是一场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