D题dfs序O(nm)做法

def solve():
    n, m = MII()
    a = LII()
    b = LII()
    g = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = GMI()
        g[u].append(v)
        g[v].append(u)
    f = [[0] * (m + 1) for _ in range(n + 1)]
    sz = [1] * n
    c = []
    def dfs(x, fa):
        for y in g[x]:
            if y == fa:
                continue
            dfs(y, x)
            sz[x] += sz[y]
        c.append(x)
    dfs(0, -1)
    for i in range(1, n + 1):
        u = c[i - 1]
        for j in range(m + 1):
            v1 = f[i - 1][j - b[u]] + a[u] if j >= b[u] else 0 # 选
            v2 = f[i - sz[u]][j] if i >= sz[u] else 0  # 不选
            f[i][j] = max(v1, v2)
    print(f[n][m])
    return