Introduction

当我们想要同时完成

  • 求树上$u$到$v$的权值和
  • 将树上$u​$到$v​$的权值都加$d​$

这两种操作时,会怎么做呢?

相信我们对于这两种操作分别都会解决,但是如果一旦放到同一道题里,我们就会束手无策了。

树链剖分便由此而来了。