提供一些数据供代码调试。
12
1 2
2 3
1 4
4 5
3 6
5 7
5 8
8 9
1 10
7 11
10 12
ans: 10
断边 4-5,连边 11-6/11-12/9-6/9-12 均可,这组数据的问题是注意从祖先转移过来。
12
1 2
2 3
1 4
3 5
5 6
3 7
4 8
1 9
9 10
5 11
7 12
ans: 9
断 1-2/2-3 均可,这个数据的问题在于从祖先转移更新的时候注意祖先要是端点。
12
1 2
1 3
2 4
3 5
2 6
3 7
4 8
6 9
5 10
3 11
11 12
ans: 9
可以断边 1-2/1-3,这组数据的问题在于需要分类讨论祖先子树的直径是否经过祖先。
具体做法可以看我的题解。