调了两天,总结一下踩到的所有坑。
- 圆方树空间要开两倍(否则 RE + MLE)。
- 虚树的建树数组要开两倍(否则 RE)。
- 注意 dfn 是圆方树的 dfn,不是原图 tarjan 的 dfn。
- 注意虚树每次的清空。
- 如果你用
memset()请将memset(a,0,sizeof(a))改为memset(a,0,sizeof(int)*n),否则可能 TLE
- 如果你用圆方树两点距离计算虚树边距离,注意两个端点为圆点或方点的情况。
- 注意是否将不在任何两个关键点之间路径上的点算进了答案。
- 方点不能割。
还有,感觉这个时限有点夸张,其实所有点都可以在 1s 内通过。