BZOJ 3052: [wc2013]糖果公园

正文索引 [隐藏]

Description


 

Input

Output


 

Sample Input


 

Sample Output

HINT

 

题解

在写了苹果树的基础上再来写糖果公园就简单多了!这是暴力的O(n)的价值转移+O(t)的时间转移。
我们这么想对于每个修改,我么只需要把时间恢复到走那条路径时候的时间就可以了,然后和苹果树一样莫队转移。
我还是用的是Sqrt(n)的子树分块,时间和空间都还比较充足!
P.S.这竟然一遍写出来好开心!第一次提交忘记去掉freopen了、、QAQ

代码