树链剖分是极其恶心的要用到其他数据结构的一种数据结构(或者说处理策略)。在应用之前,需要熟练掌握树形Dp,Dfs,Dfs序,对数相关概念,线段树/Splay/...。这道题就要用到树链剖分。

题意

给定一棵n节点树(n<=5×10),和q次操作(q<=105),操作有两种:1.将连接a,b的链上的所有节点的权值加c;2.求点a的权值。有多组数据。

思路

由于LCA我们最快可以O(1)求,但是更新权值需要O(n)的复杂度。那么暴力算法的复杂度就是O(qn),不再可承受范围内。
所以我们有这么几个思路:
1.讨论如何用数据结构优化区间修改操作。
2.讨论如何在快速求出LCA的同时还可以快速更新。
于是傻×都可以看出来这个要用树链剖分。具体神码是树链剖分详见本博客的另一篇教程。
简单来讲,我们为了可以比O(n)快地求LCA并且可以成段更新,我们将树划分成两种颜色不同的边。同种颜色的相连边可以保存深度最小的点是谁,于是就可以跳跃着求出LCA,过程与倍增类似。通过良好的划分方式,我们可以得到一个双色的树,这棵树的每一个点到根节点只需要跳跃logn级别的次数。对于每一次跳跃跳过的链,我们可以依次将链上的节点编号,放入线段树中。每一条边的节点在线段树中是连续的。所以可以logn修改。这样我们就得到了O(nlognlogn)的解法。