滴滴笔试AK（9月28日）

T1

n, a, b, c = map(int, input() .split())
cache = dict()

def dfs(i, a ,b, g):
    if (i,a, b,c) in cache:
        return 0
    ans = int(a + b > c and a + c > b and b + c > a)
    if n < i:
        cache[(i,a,b,c)] = ans
        return ans
    if c > i:
        ans += dfs(i + 1,a, b, c - i)
    if b > i:
        ans += dfs(i + 1,a, b - i, c)
    if a > i:
        ans += dfs(i + 1,a - i, b, c)
    cache[(i, a,b,c)] = ans

    return ans

print(dfs(1,a, b, c))

T2 换根dp，先dfs一次算出根为0时候的答案，记录一下每个节点的子树的大小，然后换根，计算的时候可以O(1)转移根节点

def dfs1(root):
    sz = 1
    for to in adj[root]:
        if vis[to]:
            continue
        vis[to] = 1
        sz2, ans2 = dfs1(to)
        sz += sz2
        ans[root] += ans2
    ans[root] += sz - 1
    szv[root] = sz
    return sz, ans[root]

def dfs2(root):
    for to in adj[root]:
        if vis[to]:
            continue
        vis[to] = 1
        t = ans[to]
        ans[to] += n - szv[to]
        ans[to] += ans[root] - t - szv[to]
        dfs2(to)

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
p = [-1] * n
szv = [0] * n
ans = [0] * n

xv = list(map(int,input().split()))
for i in range(1, n):
    x = xv[i-1]-1
    p[i] = x
    adj[i].append(x)
    adj[x].append(i)

vis = [0] * n
vis[0] = 1
dfs1(0)

vis = [0] * n
vis[0] = 1
dfs2(0)

xv = list(map(int,input().split()))
for i in range(m):
    v = xv[i] - 1
    print(ans[v], end=" ")