树上二点路径异或和的 $O(n -\sqrt n)$ 做法！
故事是这样的，一道模拟赛题。
给定一棵树，
q 次询问查询树上两点路径异或和。
这可真是太简单了！你很容易想到用复制树剖模板的方法来快速切掉这题。但模拟赛是断网的，你只能靠自己了。
你注意到有一个链的性质。考虑将链转化为序列，你很容易想到了将这个序列分为
但仅此部分分还不够，你要更多的分数！你将目光转向了树。有一种很简单的方法，就是暴力对所有的链都做一次莫队分化。然而这样子遇到菊花就炸了。所以你要一种新的方法！
你想到了一种简单的方法，将所有长超过
然而这样还是极慢。你考虑使用类似于链分治的方法。考虑抽出最长链，并判断剩下到它的距离！然而一直反复计算是复杂的。你注意到有些链可以直接丢掉，你发现直接维护儿子最长链是极其简单的！剩下的链判断长度即可。每条链单独维护前后缀！于是我们将复杂度做到了预处理
然后由于
怎么是黄题？！