题解 P3525 【[POI2011]INS-Inspection】

· · 题解

思维定式？

这是我们今天考试的题目...

大家都搞什么换根dp求最长链，有必要吗？？？

如果一个点不是重心，那么答案一定是-1。

否则，就是深度和-最长链。

注意，如果重心子树最大值为\frac n2，那么最长链只能在这个子树里选。

由于一棵树重心最多只有两个，我们暴力做就好了。

代码就不贴了，很好写...