树链剖分

#**树链剖分** ###**一、概念** 把树剖成链再操作 博客安利：http://www.cnblogs.com/chinhhh/p/7965433.html ###**二、实现** 维护7个不同数组，通常和线段树一起使用 ###**三、题目** ####**1、模板题** P3384 【模板】树链剖分 https://www.luogu.org/problemnew/show/3384 P3178 [HAOI2015]树上操作 https://www.luogu.org/problemnew/show/3178 P2590 [ZJOI2008]树的统计 https://www.luogu.org/problemnew/show/2590 P2146 软件包管理器 https://www.luogu.org/problemnew/show/2146 P2420 让我们异或吧 https://www.luogu.org/problemnew/show/P2420 ####**2、应用题** P3950 部落冲突 https://www.luogu.org/problemnew/show/3950 P3038 牧草种植 https://www.luogu.org/problemnew/show/3038 ###**四、做题经验** ####**1、线段树加法进行下放懒标记和打标记时要乘区间长度** ```cpp if(l>=gl&&r<=gr) { t[now]=(t[now]+(r-l+1)*z)%P; lazy[now]=(lazy[now]+z)%P; return; } ``` ```cpp t[now<<1]=(t[now<<1]+lazy[now]*(mid-l+1))%P; t[now<<1|1]=(t[now<<1|1]+lazy[now]*(r-mid))%P; ``` 这是P3384 模板，当时还请zsy帮忙调了 ####**2、把边权下放到点权的时候注意临界情况** ```cpp if(Query(1,1,n,dfn[y]+1,dfn[x]))printf("No\n"); ``` 这是P3950 部落冲突，把边下放到点的时候，对于LCA特殊处理，比如说点A和B的LCA是K，K上方发生战争于是标记在K，但A和B还是联通的，所以查询时要忽略K，即+1。 ####**3、注意lazy是非零即放，那么不要打叹号** 查错时可以考虑一下 标签:树链剖分