拼多多王国的城市和道路的拓扑结构比较特别，是一个树状结构：

1. 每个城市是树的一个节点；
2. 城市之间的道路是树的一条边；
3. 树的根节点是首都。

拼多多周年庆马上就要到了，这是拼多多王国的一个大日子。为了活跃气氛，国王想在道路上布置花灯。花灯可是很贵的东西，尽管国王想要在所有道路上都布置花灯，但是如果要花太多钱的话，是过不了财政大臣那一关的。国王把这个计划告诉财政大臣，最后他们商讨出来这么一个方案：

1. 一条道路要么不布置花灯，要么整条布置花灯，不能选择其中的某一段布置；
2. 除非没有道路通向首都，否则至少为一条通向首都的道路布置花灯；
3. 所有布置花灯的道路构成的子图是连通的，这保证国王从首都出发，能通过只走布置了花灯的道路，把所有的花灯游览完；
4. 如果某个城市（包括首都）有大于等于2条道路通向子城市，为了防止铺张浪费，最多只能选择其中的两条路布置花灯；
5. 布置花灯的道路的总长度设定一个上限。
   在上述方案下，国王想要使得布置花灯的道路长度越长越好，你帮国王想想办法。

输入描述
每个测试输入包含1个测试用例。
输入的第一行是一个正整数m，0<m<=9900，表示布置花灯的道路的总长度的上限。
输入的第二行是一个正整数n，n<=100，表示城市的个数。
紧接着是n-1行输入，每行三个正整数u、v、d，表示下标为u的城市有一条长度为d的道路通向它的一个子城市v，其中0<=u<n，0<=v<n，0<d<=100。

输出描述
输出一个正整数，表示能布置花灯的道路长度的最大值

输入例子1：

5
5
0 1 1
0 2 2
0 3 3
0 4 4

输出例子1：

5

思路

dfs搜索所有可能路径的长度值。包括一个节点所有的儿子中选1个儿子，选2个儿子的情况（最多只能选择两条路布置）。
步骤如下：

1. 根据输入，得到所有节点的父节点字典和两两节点连通关系字典；
2. 找到根节点；
3. children集合维护每个节点的所有孩子节点，sets记录每个子节点的候选路径列表，对于候选路径集合，枚举三种情况：

• 一个子节点都不选：则cand集合里面插入0；
• 只选择一个子节点：枚举所有子节点，将子节点候选列表里的所有路径长度都加上其父节点到此子节点路径长度，然后再插入父节点的候选集合列表；
• 选择两个子节点：枚举所有两两子节点组合，把两子节点的候选集合排列组合相加，再加上各自到父节点路径长度，存入父节点候选集合列表。

4. 找出根节点候选集合中不超过上限值的最大值，即为答案。

代码

from collections import defaultdict


limit = int(input())
city = int(input())
tree = defaultdict(lambda :dict())
parent = {}
visited = {}
root = None

# build tree
for _ in range(city - 1):
    s = input().split()
    u, v, d = int(s[0]), int(s[1]), int(s[2])
    if d > limit:
        continue
    if not root:
        root = u
    parent[v] = u
    tree[u][v] = d

# find root
while parent.get(root, -1) != -1:
    root = parent.get(root)
    
'''
cand：候选队列，存放当前节点的所有可能路径长度
children：存放以当前节点为根节点的所有的子节点
sets：存放以当前节点为根节点的子树下，每个孩子节点的候选队列
'''
def dfs(u):
    if u not in visited:
        cand = set()
        cand.add(0)
        if u in tree:
            sets = []
            children = []
            for v in tree[u]:
                children.append(v)
                sets.append(dfs(v))
            for i in range(len(sets)):
                d = tree[u][children[i]]
                for c in sets[i]:
                    if d + c <= limit:
                        cand.add(d + c)
                for j in range(i + 1, len(sets)):
                    d2 = tree[u][children[j]]
                    for c in sets[i]:
                        for c2 in sets[j]:
                            if c + c2 + d + d2 <= limit:
                                cand.add(c + c2 + d + d2)
        visited[u] = cand
    return visited[u]


print(max(dfs(root)))