标签:树链剖分

【题解】 软件包管理器 树链剖分 NOI2015 BZOJ – 4196 LUOGU – 2146

1. 题目

LUOGU传送门= ̄ω ̄=
BZOJ传送门= ̄ω ̄=

2. 题解

学lct太累娱乐一下
获得了满满的满足感
树链剖分模板题
首先install操作就是先查询根节点(0)到当前节点的路[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 染色 树链剖分 LUOGU – 2486 BZOJ – 2243

1. 题目

LUOGU传送门= ̄ω ̄=
BZOJ传送门= ̄ω ̄=

2. 题解

没什么好说的,树链剖分模板题
线段树记录区间左右端点颜色,合并区间的时候看左区间的右端点和右区间的左端点是否相同,相[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 染色 (bzoj2243) 树链剖分 -boshi

题意:给定一棵树,每个节点有一个颜色(105内个点)。有很多询问操作(105内个操作),分别为将两点之间的路径上的点的颜色全部设为c,以及询问两点之间的路径上有多少子段(子段是一段连续的同色点)。

[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 旅游 (BZOJ2157) 树链剖分 -boshi

Warning! : 一个函数如果没有返回值,你也有可能得到正确的结果。因为函数调用完了之后你要返回的东西也许就在内存空间里。但是这么提交你肯定会WA。别问我怎么知道的。


以下这个函数可以自动将[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment

【题解】 Aragorn’s Story 树链剖分 HDU – 3966

1. 题目

传送门= ̄ω ̄=

题意:

I C1 C2 K: 把C1与C2的路径上的所有点权值加上K

D C1 C2 K:把C1与C2的路径上的所有点权值减去K

Q C:查询节点编号为C的权值[......]

[继续阅读= ̄ω ̄=]

Read MoreView 2 Comments

【算法】 树链剖分 —— 蒟蒻XZY

1. 前言

如果给你一棵树,求点u到点v路径上点的权值之和,你可能会说:倍增啊!

那如果出题人:我还要你支持修改某个点的权值!

或者再j一点:我还要你支持修改点u到点v路径上点的权值!

那就得[......]

[继续阅读= ̄ω ̄=]

Read MoreView 9 Comments

【题解】 树的统计 树链剖分 ZJOI2008 BZOJ – 1036

1. 题目

传送门= ̄ω ̄=

2. 题解

树链剖分模板题。
先剖树成链,再用线段树维护一条一条的链。
线段树连懒惰标记都不用,单点修改

代码:

[crayon-5a5ed6f66350d55[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Aragorn’s Story 树链剖分 -boshi

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

题意

[......]

[继续阅读= ̄ω ̄=]

Read MoreComment