【洛谷1505】旅游

基本上是一道树剖模板题。但是WA\color{red}WA了一上午才终于AC\color{green}{AC}

原题

这道题是边权,不过因为这是一棵树,可以把边权赋予这条边上深度更大的节点,就变成了树剖模板题。

但是这道题的push down操作是真的麻烦。

单点更新修改值,区间更新取相反数,区间查询,维护一个懒惰标记tagN表示取相反数。

阅读更多

ymoi集训-树链剖分

树链剖分解决什么问题

先看这样的一个问题:

给出一棵nn个结点, 每个结点有点权, 要求支持:

1 u v x 将树上uvu\rightarrow v这条链的所有结点点权增加xx
2 u xuu的子树的所有结点的点权增加xx
3 u v 询问uvu\rightarrow v这条链的所有结点点权和
4 u 询问uu的子树的所有结点的点权和

n,q1×105n,q\leq 1\times 10^5

这个问题看起来很像线段树的题,不过这是在树上操作,所以我们要用树链剖分。

阅读更多
Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×