【讨论】关于SDOI D2T2 解法

以下内容都是在上课的时候口胡在草稿纸上的，还没有实现。

我一开始只考虑了链上的做法，本质上是个裸的区间加和区间求和。题目的空间限制相当于直接砍掉了线段树等空间大常数 $O(n)$ 做法，单纯存下节点权值就要 26mb 的空间（链上可以不考虑存储树的形状），所以可以考虑空间 $O(\sqrt n)$，时间 $O(q \sqrt n)$ 的分块，经过计算可以通过。

然后我想到把这个做法推广到树上，具体是做一次朴素的树剖，但是对剖完的序列不用线段树而是分块维护，时间复杂度 $O(n+qlogn\sqrt n)$ ，且这个上界不紧，时间上是能接受的。

然而问题出在了空间上。对于朴素的树剖，每个节点我们要维护 7 个元素，直接给空间乘上了7的常数，无法接受。

我想知道往分块这个方向想有没有问题，以及想到树剖配分块这一步怎么优化下去。

希望场内外的大佬们能来帮忙看看，如果有别的做法也欢迎来分享一下，感激不尽。