题解 P4408 【[NOI2003]逃学的小孩】

2018-08-21 20:01:50


题目要求 $min(C\to A,C\to B)+A\to B$ 。

考虑最大化两部分。第二部分容易看出,求出树的直径即可。此时确定了 $A$ 、 $B$ 。

对于第一部分,枚举 $C$ 点,求出最大的 $min(C\to A,C\to B)$ 即可。

答案为两部分相加。 注意开long long。

代码见蒟蒻的blog