from functools import lru_cache from math import sqrt @lru_cache(None) def dfs(u, parent, b): """ param: b: 当前节点是否已经染色 """ res = 0 t = [] # (权值,染色的贡献,不染色的贡献) for v in g[u]: if v != parent: t.append((ws[v], dfs(v, u, True), dfs(v, u, False))) sumy = sum(y for w, x, y in t) if b: # 当前已经染色,计算所有孩子节点没染色的...