Open xehoth opened 7 years ago
https://blog.xehoth.cc/NOIP2015-Transport/
分析求出每条路径两个端点的最近公共祖先,进而求出每条路径的长度。二分一个答案xxx,所有长度>x>x>x的路径上都至少需要删去一条边。对这些路径求交,最优方案一定是删去路径交中长度最大的边,如果删去最大的边后,最长的路径仍不满足≤x \leq x≤x,则答案xxx不合法。
https://blog.xehoth.cc/NOIP2015-Transport/
分析求出每条路径两个端点的最近公共祖先,进而求出每条路径的长度。二分一个答案xxx,所有长度>x>x>x的路径上都至少需要删去一条边。对这些路径求交,最优方案一定是删去路径交中长度最大的边,如果删去最大的边后,最长的路径仍不满足≤x \leq x≤x,则答案xxx不合法。