T3
还需要再琢磨琢磨。
T4
首先我们考虑一个节点 \(u\) 对答案的贡献。假设 \(u\) 子树内的数形成了若干个极大的连续段 \([l, r]\)，若 \([ql, qr]\) 与某个 \([l, r]\) 的交集至少为 \(k\) 就有 \(dep_u\) 的贡献。
所以我们来考虑如何维护这个极大的连续段。一个比较显然的方式是并查集，加入一个元素 \(x\) 后，只可能将 \(x - 1, x, x + 1\) 所在的集合连到一起，只需要用 \(x\) 现在所在的集合进行贡献。
但是我们也不可能将每次将 \(u\) 内所有元素都扫一遍，那就爆了。这时我们就可以想到启发式合并，每次 \(u\) 从 \(son_u(u 的重儿子)\) 继承过来，这样总共至多加入 \(O(n \log n)\) 的元素了。而且这样做显然是正确，因为只会漏算只包含 \(son_u\) 子树的连续段，而这个显然 \(son_u\) 贡献更优。
所以我们就拥有了 \(m(m \le n \log n)\) 个可能贡献的区间，接下来就比较好办了。对于 \(l < ql\) 的，只需要满足 \(r \ge ql + k - 1\)；对于 \(l \ge ql\) 的，只需要满足 \(r - l + 1 \ge k, l \le qr - k + 1\)，化简一下 \(ql \le l \le qr - k + 1 \&\& r - l + 1 \ge k\)。就是两个二维数点，搞个线段树即可在 \(O((m + q) \log m)\) 的时间内解决。
所以我们就拥有了时间复杂度最坏为 \(O(n \log^2n)\) 的做法，其实已经能过了。但是还有更优秀的做法。
对于后半部分其实没办法优化了，只能优化前半部分。我们仔细分析，只有当两个集合合并时才有会产生一个贡献区间，而总共只有 \(n\) 个数，也就是最多只有 \(O(n)\) 个有用的区间。
但是启发式合并已经没有前途了。不过也许你知道这个结论：\(dep_\text{LCA*(l, r)} = \min\limits_{i = l}^r dep_{\text{LCA(i, i + 1)}}\)。那我们可以求出所有 \(\text{Lca(i, i + 1)}\)，用单调栈（笛卡尔树）求出这个它为最小值的区间，这就可以得到 \(O(n)\) 个区间了，不难发现它是包含了所有情况的。
时间复杂度来到了 \(O(n \log n)\)。
评价
一条链的部分分有利于可以让我们想到使用若干个有用的贡献区间 \([l, r]\)来贡献答案。（似乎容易去想线段树上二分，而非并查集，并且容易误导人，以为新增的区间一定包含 \(u\)，反正我被坑了。）
两只 \(\log\) 的做法还是比较粗暴的，单 \(\log\) 需要知道一个结论。（我想到另一个结论：找 \(dfs\) 最小和最大的算 LCA，然后没有任何前途）
似乎搞完 SA 后也一般是笛卡尔树或者并查集进行合并。