对这道题作法的一点提示

作为一个看了树套树标签进来,打了半天熟练剖腹树链剖分的逗比,我看了别人网上的题解才发现我的复杂度爆炸... 这题的标算是块状树,即在树上分块维护,复杂度$O(n*sqrt(n)*log(n))$. 数据很大,不卡常是很难过的.

然而实际上,大多数被卡的程序都T在前两个点,后面的点都能通过.

..所以我要说的是,用这道题数据的特性AC.

来讲讲我做这题的心路历程吧

第一次提交:自信地打了一发树链剖分维护的树套树,一遍过样例,提交

结果是: 嗯,没有WA

那就卡卡常再交

...

看了一波网上的题解

嗯,是树上分块

( 打脸

吃过中饭 : 嗯,打一波暴力吧

(惊奇!

AC[20]∪AC[80]=AC[100]

然后..

我就开始二分前两个点$n$的范围

如你所见,到最后一次测试,前两个点的T变成了WA

所以----

前两个点的n,刚好就是30000

接下来的事就好办了