codeforces：B. Zero Tree【贪心的树状dp + dfs + bootstrap】

题目

https://codeforces.com/problemset/problem/274/B

输入 n(≤1e5)，表示一棵有 n 个节点的树。

然后输入 n-1 条边：这条边所连接的两点的编号（从 1 开始）。

最后输入 n 个数，表示每个节点的值 ai。

每次操作，你可以选择一个包含节点 1 的连通块，把所有点的值都 +1 或都 -1。

输出把树上所有节点的值都变为 0 的最少操作次数。

分析

从0开始dfs，记录fa，防止反向访问
对于所有儿子节点而言，父节点可以记录他们各自变成全0所需要的最大+1和-1次数plus，minus
然后选一个最大作为待定的，因为其他的都可以乘坐最大的便车
然后看看父节点会在这plus和minus下变成什么数curr
如果curr大于0，需要额外减
如果curr小于等于0，需要额外加（注意符号）

ac code

import sys
from collections import defaultdict
input = sys.stdin.readline

# --------------------
# 手写栈模板
# 克服py栈太浅的问题
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
# --------------------


def solve():
    n = int(input())
    g = defaultdict(list)
    for _ in range(n - 1):
        a, b = list(map(int, input().split()))
        g[a - 1].append(b - 1)
        g[b - 1].append(a - 1)
    v = list(map(int, input().split()))
    ans = 0


    # 返回的是当前子树变成全0的最少次数
    # 最少次数：【加的次数，减的次数】
    @bootstrap
    def dfs(node, fa):

        # 保留最大的
        # 这样其他小的都能顺道完成
        plus = minus = 0
        for nextNode in g[node]:
            if nextNode == fa:
                continue
            p, m = yield dfs(nextNode, node)
            plus = max(plus, p)
            minus = max(minus, m)
        # 当前节点被迫修改（因为必须连上1）
        curr = v[node] + plus - minus
        if curr > 0:
            yield plus, minus + curr
        else:
            # 小心curr是负数的情况
            yield plus - curr, minus

    # 最小的修改对应的+1修改和-1修改
    print(sum(dfs(0, -1)))



if __name__ == '__main__':
    solve()

总结

经典贪心（选最大的其他搭便车）
然后dfs + bootstrap优化