如何用bitset和DFS序实现线段树解决Codeforces633G Yash And Trees问题？

本文共计1051个文字，预计阅读时间需要5分钟。

传递门：点击打开链接主题：给你一棵树，根节点为1，有两种操作，第一种是给u节点所在的子树的所有节点值加x，第二种是询问，假设v是子树u中的节点，询问该节点值是否满足某种条件。

传送门：​​点击打开链接​​

题意：给你一棵树，根节点为1

有2种操作，第一种是给u节点所在的子树的所有节点的权值+x

第二种是询问，假设v是子树u中的节点，有多少种质数满足av = p + m·k

其中p<m

思路：首先用DFS序，把树弄成线段树来表示，这种做法十分常见就不多讲了

因为m<=1000,我们用bitset保存av%m的值

每次对子树增加权值的时候，只需要修改懒惰标记，来记录增加的大小

然后直接把bitset利用位运算来完成循环移动就行了。

这道题只要能熟练运用bitset，对DFS序的线段树有一定的了解，应该是没很大问题的。