hdu 5915(The Fastest Runner Ms. Zhang-基环外向树+贪心dp)

题意:给一颗基环外向树(边权均为1),求把所有点走过一遍的最小路径长,并在满足上述条件的前提下给出字典序最小的(起点,终点)。

\(1\le n \le 10^5 \)

套板子先找出环,然后树形dp出每个点下方的最远路与次远路,以及它们的终点编号。

设环的长度为c

不难发现答案存在2种情况:

  1. 起点终点在同一颗树上,\(ans= 2n-c-dis(S,T)\)

  2. 起点终点不在一颗树上,ans=2n-2-dis(U,V)-dis(S,U)-dis(V,T)

    这个时候
    hdu5915

于是只要维护最值来回扫描一遍即可