对于本题数据的一些说明

P3806 【模板】点分治 1

一扶苏一 @ 2020-02-08 00:56:40

谷的评测机是不存在爆栈一说的，RE 一般只可能是产生了段错误或返回值异常等。
树的所有边权权值总和达到了 10^8，但是询问只到了 10^7，因此在统计子树内路径权值时，需要在经过权值大于 10^7 的时候及时返回，否则由于用了桶来统计路径，大于 10^7 的权值会爆数组，第一篇题解在 #7 会 RE 就是这个原因。如果您也 RE 了，不妨检查一下这里。
如果您是每次询问都点分一次然后被卡常了，可以考虑建出点分树后统一处理所有的询问（也可以像第一篇题解一样一边点分一边处理询问），因为本题点分做法的时间复杂度是 O(nm \log n)，但是点分的复杂度是 O(n \log n)，如果只点分一次，它的巨大常数是不会乘到总复杂度里面去的，这样对效率有非常大的提高。

by Aw顿顿 @ 2020-02-08 14:40:51

前排资瓷+无序列表可以多换几个行

by 九思 @ 2020-02-09 16:00:05

我觉得第二篇题解是O(N^2)的但是我没有证据。。可能是我码力太弱了。。求解释QAQ

by YellowBean_Elsa @ 2020-03-11 20:58:59

第一篇题解我测了一下#7 没有RE啊

by YellowBean_Elsa @ 2020-03-11 20:59:16

@YellowBean 但是本地会RE

by Loliconrz @ 2020-03-15 03:03:05

洛谷管理员将会流芳百世！！！

by Loliconrz @ 2020-03-15 03:03:42

@DaRk_MasTeR 太辛苦了orz，感谢管理

by 文·和 @ 2020-04-02 20:13:03

后排考古

by xh39 @ 2020-04-09 19:40:47

hpkg.

by the_same_prayers @ 2020-05-15 20:40:44

相信我，只要第一篇题解数组开15000000和02，既不会TLE也不会MLE，#7 49ms轻松过

by 幻之陨梦 @ 2020-05-18 10:02:03

考咕