感觉正解是 O(n) 的换根 DP，你的写法
是O(n ^ 2)的，无法通过 5e4 的数据是合理的，正解时间复杂度是线性的
by zhuoxingmu @ 2023-11-09 16:49:40
@[huozhenyi](/user/784944)
by zhuoxingmu @ 2023-11-09 16:50:02
@[zhuoxingmu](/user/421155)
我觉得有剪枝，应该可以过。
by huozhenyi @ 2023-11-09 17:02:48
@[zhuoxingmu](/user/421155) 每次只搜索当前点的子节点不是可以看作减少了一些不必要的点吗
by huozhenyi @ 2023-11-09 17:04:18
@[huozhenyi](/user/784944)
你的代码的时间复杂度分析应该是外层的 O(n) 次枚举起点，和每次 O(n)的 dfs，你所说的搜索当前点的子节点是指 dfs时每个点最多被访问一次，事实上dfs中每个点也只会被访问一次，当然都是指单次的情况下。
所以总体的时间复杂度是满的O(n ^ 2)
by zhuoxingmu @ 2023-11-09 18:08:53
@[zhuoxingmu](/user/421155)
哦哦，谢谢讲解。
by huozhenyi @ 2023-11-09 18:14:01