对于这类问题，我们有一种比较通用的解法是设定一个贡献的充要条件。我们通常会在若干个都能产生某一贡献 \(p\) 的元素 \(a_1\dots a_k\) 上定义一种小于关系 \(R\)，每次只让这些元素中的极小值进行贡献。具体来讲我们可以对每个元素求出它上/下一个比它“小”的元素 \(pre_x,suf_x\)，那么这个元素会对询问 \([l,r]\) 产生 \(p\cdot[pre_x<l\and suf_x<r\and l\le x\le r]\) 的贡献，这看起来是个三维偏序，但实际上是二维的，可以用扫描线一个 log 维护。
接下来我们的问题变成如何给定这样一个序关系。自然的想法是钦定一个“C-块”里最浅且编号最小的节点进行贡献，这等价于 bfs 序更小。
问题转化成对于每一个点求 C 邻域内 bfs 序比它小的前驱后继，有三条限制要满足：
- \(dis_u+dis_x\le C\)
- \(bfn_x<bfn_u\)；
- \(x\) 是 \(u\) 前驱。
考虑双指针维护第一条限制，线段树维护区间 \(bfn\) 最小值，在线段树上二分计算。
总复杂度 \(O(n\log^2n+q\log n)\)。
卡常没卡过，悲。