一棵边权均为1的无根树, q个询问: 给出k个关键点, 每个点隶属于与它最近的关键点, 求每个点和它上司的距离的最大值. (1 ≤ n,q,Σm ≤ 10^5) 做过 [bzoj 3572] [Hnoi2014]世界树 之后, 发现思维量没有变多, 单纯是情况变复杂了.
换一个问法: 求 max { 每个关键点管的点和它的距离的最大值 }. 和数目不同, 最大值不能直接做减法......主要思路是把原来做减法的地方替换成查 ST 表.
考虑虚树上的边 (u,v), 上面的一段隶属于 x. 分两类: 
据此, 我们发现, 用 ST 表在 DFS 序上维护 dep 的最大值, 再树链剖分一下, 同样用 ST 表维护 dep[w] - 2 dep[t] (w 在 t 的轻子树中) 的最大值就可以了.
点的贡献简单些. 直接查不在虚树中的子树的最大深度即可.