这题,连写带调用了 4h,虽然很累,但是我认为是值得的。在这里,我将列举常见错误,衷心希望后来的同学不要重蹈覆辙。
(1) 检查求树的直径的树形 dp 函数。我将统计最大值的变量 res 的赋初值写在了函数里面导致 WA.
(2) 检查是否考虑了直径不穿过那个环的情况。
(3) 注意对重边的处理。我们需要在重边中取边权最大的,此时基环树森林中的一些会退化成树,需要特判。
(4) 不开 long long 见祖宗。
(5) 检查单调队列是否在开始时把决策 1 放入队列并从 2 开始枚举。
(6) 枚举森林中的每一颗基环树时,检查是否清空相关变量和数组。
(7) vis 数组不能与找环的操作合并,否则可能会少标记很多点。需要单独拉出来写。
这些大致涵盖了所有常见错误了。最后放几组我对拍时拍出错的 hack 数据:
in1:
10
4 10792
5 13372
10 23527
7 30208
6 17197
7 5876
2 31850
4 27969
4 5686
1 15428
out1:
142374
in2:
8
2 15076
1 6451
8 9347
1 28588
7 11980
8 13715
8 2292
6 10087
out2:
71651
in3:
5
2 1
3 1
1 1
2 99999
2 99998
out3:
199997
希望以上能帮到和我一样痛苦的调试的人。