标签:树链剖分

Luogu P3313 [SDOI2014]旅行(树剖)

huangkui 2018年2月10日 No Comments Problem , , ,

题目链接:传送门 Description S国有N个城市,编号从1到N。城市间用N-1条双向道路连接,满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教,如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。 为了方便,我们用不同的正整数代表各种宗教, S国的居民常常旅行。旅行时他们总会走最短路,并且为了避免麻烦,只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级,旅行者们常会记下 […]

LCA总结

huangkui 2017年8月8日 1 Comment Algorithm, 未分类 , , , , , ,

这段时间一直在学习LCA的各种算法,下面就对LCA的各种算法进行一次总结: 问题概述 LCA(最近公共祖先)指的是在一棵树上两个节点的最近的公共祖先(这句话好像跟没说差不多),也就是深度最深的公共祖先。LCA的适用范围非常广,在许多较难的与树有关的题中都会需要用到。因此,掌握求LCA的方法是非常重要的。

树链剖分

huangkui 2017年8月8日 No Comments Algorithm, 未分类 ,

开始一直以为树剖是一个非常高大上的数据结构,怕学不会,学完之后发现树链剖分其实特别简单 问题概述 树链剖分(也叫轻重链剖分),是解决在树上进行区间修改、查询这一类问题的一个算法。事实上,树链剖分就是由两遍dfs预处理+其他数据结构(如线段树、树状数组等)构成的。以洛谷P3384为例,如果我们直接将每个节点按照dfs的顺序加入线段树中的话,每次修改或是查询都需要将u和v的路径之间所有的节点都处理一遍。但是如果我们现将这棵树进行特殊的编号,使得在查询 […]

Page 1 of 1