Google Kickstart 2021 Round B Truck Delivery题代码错误排查

1. 边的方向构建逻辑完全错误
   你默认父节点编号一定大于子节点，只要road[0] < road[1]就交换两个端点的位置，这个假设没有任何题目依据。题目中的树是以1为根节点，边是无向给出的，你不能通过编号大小判断父子关系，这会导致大量边的方向被反转，递归查找从查询节点到根节点的路径时，根本找不到对应的边，自然不会把符合条件的罚款加入列表。
   比如Case2的第一个查询，就是因为回根的边被你反转了，fines为空才输出了0，和你观察到的现象完全吻合。

2. 全局变量导致的逻辑隐患
   solve函数中直接使用全局作用域的roads、w、fines变量，虽然你当前的代码结构暂时没触发冲突，但这种写法极容易出现变量污染，后续调整逻辑时很容易出现非预期错误。

3. math.gcd传参错误
   Python标准库的math.gcd只支持接收2个整数参数，你用math.gcd(*fines)的写法，一旦fines长度大于2，代码会直接抛出参数数量不匹配的异常，你当前没报错只是因为错误的边方向逻辑导致fines长度始终不超过2。

• 硬编码输入重定向：sys.stdin = open('input.txt', 'r') 提交到OJ时会直接报错，应该通过参数控制是否开启本地读文件，或者提交前删除这行代码。
• 递归函数没有做参数封装：把路径、权重限制、罚款列表都作为参数传递，而不是用全局变量，可读性和可维护性都会好很多。
• 没有构建邻接表：每次递归都遍历整个roads列表查找对应节点的边，时间复杂度极高，应该提前把边存成邻接表adj[u] = [(v, limit, fine)]的格式，查找效率直接从O(n)降到O(1)。
• 无意义的排序操作：你对roads做了倒序排序，但后续遍历逻辑完全没有利用排序的特性，属于多余的性能损耗。
• 结果拼接用字符串累加：Python中字符串是不可变对象，循环累加字符串会产生大量临时对象，应该用list存储结果最后用join拼接。

内容的提问来源于stack exchange，提问作者Ber2