树上莫队算法

74 阅读 0 评论 49 点赞

我是靠谱客的博主顺心铃铛，最近开发中收集的这篇文章主要介绍树上莫队算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

简介

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

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

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

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

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

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

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

以上就是顺心铃铛为你收集整理的树上莫队算法的全部内容，希望文章能够帮你解决树上莫队算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

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