题解 | Anniversary

import sys


class Node():
    def __init__(self, _id) -> None:
        self.id = _id
        self.subnodes = []
        self.sub_paths = []
        self.path_value = 0
        self.father = -1
    def __str__(self) -> str:
        str1 = ""
        for k, i in zip(self.subnodes, self.sub_paths):
            str1 += f"[{self.id} to {k}: len {i}] "
        return f"\\{str1}\\"
    def __repr__(self) -> str:
        return self.__str__()

i = 0
m = 0
n = 0
G = []

def solve(limit, rootid):

    def get_len_set(node_id) -> set:
        out = {0}
        chiled_sets = []
        # 叶子节点直接退出
        if len(G[node_id].subnodes) < 1:
            return out

        # 把每个子节点的可能性集合先计算并 cache
        for i, v in zip(G[node_id].subnodes, G[node_id].sub_paths):
            # 得到子节点以下的所有可能性
            set_sub = get_len_set(i)
            sub_result = {0}
            # 给这些可能性加上走向这个节点的消耗
            for j in set_sub:
                result_sub = v + j
                if result_sub <= limit:
                    sub_result.add(result_sub)
            # 把可能性集合按照子节点顺序存储在列表中
            chiled_sets.append(sub_result)
        
        # 走一条路的情况
        for i in chiled_sets:
            out = out.union(i)

        # 走两条路情况
        if len(chiled_sets) > 1:
            for k, i in enumerate(chiled_sets[:-1]):
                for j in chiled_sets[k+1:]:
                    bi_result = {0}
                    for ii in i:
                        for jj in j:
                            if ii + jj <= limit:
                                bi_result.add(ii+jj)
                    out = out.union(bi_result)
                    
        return out
    
    return max(get_len_set(rootid))

for line in sys.stdin:
    if i == 0:
        m = int(line)
    if i == 1:
        n = int(line)
        G = [Node(i) for i in range(n)]
    if i >= 2:
        node_id, target_id, value = line.strip().split()
        node_id = int(node_id)
        target_id = int(target_id)
        value =int(value)
        # if node_id > target_id:
        #     tmp = node_id
        #     node_id = target_id
        #     target_id = tmp
        if target_id not in G[node_id].subnodes:
            G[node_id].subnodes.append(target_id)
            G[node_id].sub_paths.append(value)
            G[target_id].path_value = value
            G[target_id].father = node_id
    i += 1
    if i > 2 and i >= n+1:
    #     solve(m, n, G)
        # print(G)
        root = 0
        for i in G:
            if i.father == -1:
                root = i.id
        print(solve(m, root))
        i = 0
        m = 0
        n = 0
        G = []
        

使用深度优先搜索，思路是构建一个函数，获取某个节点所包含的所有走法到代价，在构建代价集合的时候就可以去掉超出限制的代价路径，比较坑的是如何去建这个树的过程。python中的集合可以非常省力。