2020牛客多校第二场C-Cover the Tree


\(很明显,记叶子节点数为s,则k=\left \lceil \frac{s}{2} \right \rceil \)

\(那么如何匹配呢?首先要选取一个非叶子节点作为根,然后对其进行dfs得到dfs序\)

\(按照dfs序大小排序得到叶子节点u_1, u_2, …, u_s \)

\(于是u_i跟u_{i+\frac{s}{2}}进行匹配,若s为奇数,则最后一个点跟根节点进行匹配 \)


 

发表评论