佛了，写了50分钟，做完了选择+AC第一道编程题，结果突然被导师抓去开会就提前交卷了🙃回头看了一下剩下的两题好像不难，补写了一下，就当练手了吧（ps. 后两题没有调试过不一定对哈）。

T1: 平衡（DFS）

对于树的每条边，记录子节点所在子树的节点个数为m，则平衡值为abs(2m - n)，用dfs遍历子树即可。

from collections import defaultdict
def solve(n, edges):
    score, fa, ans = [1] * n, [-1] * n, []
    ch = defaultdict(list)
    for u, v in edges:
        ch[v - 1].append(u - 1)
        fa[u - 1] = v - 1
    root = fa.index(-1)
    def dfs(x):
        for y in ch[x]:
            score[x] += dfs(y)
        ans.append(abs(2 * score[x] - n))
        return score[x]
    dfs(root)
    minv = min(ans)
    return minv, ans.count(minv)

n = int(input())
edges = []
for _ in range(n - 1):
    s, t = map(int, input().split())
    edges.append((s, t))
print(*solve(n, edges))

T2: 配制溶液（动态规划）

记dp[i]为溶液体积为i时物质含量的最大值，状态转移方程为

dp[i] = dp[j] + dp[i - j], if 2 * j != i;

dp[i] = dp[j] + dp[i - j] + X, if 2 * j == i.

复杂度为O(n^2)，n<=1000能通过。

def solve(volumns, weights, add, target):
    dp = [-float('inf')] * (target + 1)
    for v, w in zip(volumns, weights):
        dp[v] = max(dp[v], w)
    for i in range(1, target + 1):
        for j in range(1, i):
            dp[i] = max(dp[i], dp[j] + dp[i - j] + add * (2 * j == i))
    return dp[-1]
  
_, add, target = map(int, input().split())
volumns = list(map(int, input().split()))
weights = list(map(int, input().split()))
print(solve(volumns, weights, add, target))

T3: 袋子和球（模拟）

变量比较多，比较复杂地模拟一遍即可，注释写代码里了，复杂度O(m).

def solve(nums, colors, times, operations):
    ans, puttime = [], [0] * len(nums) # 查询答案，记录每个球的入袋时间
    rcnt = bcnt = sum = last = 0 # 红球数，蓝球数，当前总和，上一次操作时间
    for t, op in zip(times, operations):
        sum += (t - last) * (rcnt - bcnt)
        if op == 0: ans.append(sum)
        elif op > 0: 
            if colors[op - 1] == 'R': rcnt += 1
            else: bcnt += 1
            puttime[op - 1] = t
            sum += nums[op - 1]
        elif op < 0:
            if colors[-op - 1] == 'R': 
                rcnt -= 1
                nums[-op - 1] += t - puttime[-op - 1]
            else: 
                bcnt -= 1
                nums[-op - 1] -= t - puttime[-op - 1]
            sum -= nums[-op - 1]
        last = t
    return ans
    
n = int(input())
nums = list(map(int, input().split()))
colors = list(input())
m = int(input())
times = list(map(int, input().split()))
operations = list(map(int, input().split()))
ans = solve(nums, colors, times, operations)
print(len(ans), *ans)