前置知识  树链剖分 可持久化字典树  思路 首先按照 dfs 序（记作 ）插入可持久化字典树中。对于查询点  的答案，相当于从可持久化字典树中查询区间 ，由树剖可知，父亲的 dfn 区间数量级不会超过  个，所以相当于在可持久化字典树中查询  个区间的答案。 代码实现 时间复杂度 。由于每个点都要查询，树剖不会跑满，但是依旧需要注意常数。 以下代码跑了 2286 ms。（和某些  代码跑的差不多） #include <bits/stdc++.h> using namespace std; #pragma GCC optimize(3,"Ofast","inline") #defi...