今天我在写 CF1009F 的时候,线段树合并被链卡 MLE 了。
这个题大意是这样,给一棵树,对每个点求子树内离他距离为 d 的数量的点最多时,d 最小是多少,我的想法是线段树维护每个点子树内不同深度的点的个数,然后向上线段树合并,然而在一条链的数据被卡 MLE 了。
提交记录。
submission
但我的理解是,我的动态开点线段树已经事先开好了内存,而且对于这样先合并儿子,再更新自己的 dep 的写法,遇上链感觉是最不容易被卡的,每次直接把儿子的线段树根复制过来,再 log 的时间插入一个新点(由于是链,所以每个深度都不同)本地测试开的节点数是 O(n) 级别的,所以为什么会 MLE 呢/yiw