P4074 [WC2013]糖果公园 题解

P4074 [WC2013]糖果公园 题解

这道题可以说是一道树上带修莫队的板子题。虽然评级是黑的，但是树上带修莫队本身还是比较好想的。就是代码很难调。

update 2021/4/12：现在评级掉紫了。

树上莫队：

树上莫队的本质就是利用欧拉序将树上莫队问题变成序列莫队问题。

我们设 { e u l a r } {eular} {eular} 表示欧拉序序列， f i r i , l a s i fir_i,las_i firi​,lasi​ 表示节点 i i i 在欧拉序中第一次出现与第二次出现的位置。那么当询问为 x , y x,y x,y 时（此处我们规定 x x x 的深度小于 y y y），如果 l c a ( x , y ) = x lca(x,y)=x lca(x,y)=x ，那么用 f i r x , f i r y fir_x,fir_y firx​,firy​ 的区间，否则用 l a s x , f i r y las_x,fir_y lasx​,firy​ 的区间同时带上 l c a ( x , y ) lca(x,y) lca(x,y) 的贡献。为什么不是 f i r x fir_x firx​ ？因为中间出现二次的节点我们是不考虑的，因此用 f i r x fir_x firx​ 相当于浪费时间 （用时间换空间的当我没说） 。这里千万注意：序列长度是