题面 P3233 [HNOI2014]世界树 Solution 这是一道虚树妙题。 我们不妨先考虑一下每一次$O(n)$计算的暴力怎么做。 $O(n\cdot m)$的暴力肥肠简单,我们只需要做两遍dfs。考虑设$f[i]$表示离$i$最近的聚居地是什么,$MIN[i]$表示$i$到最近的聚居地的距离。我们第一遍dfs先找出$i$到它子树内的聚居地的最小距离,之后再做一遍dfs来找$i$往祖先方向后头走能走到的最近聚居地的距离即可。 观察数据范围后发现,$\sum m<=300000$,因此考虑使用虚树。 建…