Bus Routes

简述题意

一棵 nn 节点树，有 mm 条路经覆盖，问是否存在两个点，超过 22 条路径才能到达或者不能到达，若不能输出任意不合法点对。

引理

引理 11：

叶子节点必然是某条路径的端点。

引理 22：

上述问题等价于存在一个节点 uu，该节点最多使用一条路径即可到达所有节点。

分析

随意定根，找到一个叶子能到达的最深祖先，再以这个点进行引理 22 判断，O(nlog⁡n)O(n\log n) 完毕。

__END__