树上莫队算法

187 阅读 0 评论 124 点赞

我是靠谱客的博主顺心铃铛，这篇文章主要介绍树上莫队算法，现在分享给大家，希望可以做个参考。

简介

树上莫队，顾名思义就是把莫队搬到树上。

我们从一道题目入手[SDOI2018]原题识别 SPOJ Count on a tree II

题目意思很明确：给定一个$n$个节点的树，每个节点表示一个整数，问$u$到$v$的路径上有多少个不同的整数。

像这种不带修改数颜色的题首先想到的肯定是树套树莫队，那么如何把在序列上的莫队搬到树上呢？

我们考虑用什么东西可以把树上的问题转化到序列上，dfs序是可以的，但是这道题不行（无法搞lca的贡献）

有一种神奇的东西，叫做欧拉序。

它的核心思想是：当访问到点$i$时，加入序列，然后访问$i$的子树，

以上就是顺心铃铛最近收集整理的关于树上莫队算法的全部内容，更多相关树上莫队算法内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。