传送门:
题意:
给你一颗有根树,树上每个节点都有其对应的颜色,有m次询问,每次问你以点v为父节点的子树内满足某种颜色的数量大于k的颜色一共有多少种
题解:
冷静分析,胡乱分析,询问次数这么多,但是并没有修改操作,倘若把询问离线下来就好了
可是询问问的是每个点的树
这个时候我们的dfs序就可以派上用场了
dfs序:"所谓DFS序, 就是DFS整棵树依次访问到的结点组成的序列"
"DFS序有一个很强的性质: 一颗子树的所有节点在DFS序内是连续的一段, 利用这个性质我们可以解决很多问题"
通过对树进行一次dfs序操作,我们可以得到每个点他的子树所在的一段区间,这样我们就可以得到每个询问在dfs序下询问的区间了,那么我们怎么统计区间内颜色数量大于k的种类数量呢?
由于我们得到了离线下来的询问区间,用莫队算法可以在O(nsqrt(n))的时间内得到所有询问的答案
由于每次询问是查询区间内颜色种类的数量之和,我们需要用一个区间求和,单点修改的数据结构来维护莫队时统计答案和修改操作,因此我们可以用树状数组或者线段树来维护
代码:
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ > < ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */// warm heart, wagging tail,and a smile just for you!//// _ooOoo_// o8888888o// 88" . "88// (| -_- |)// O\ = /O// ____/`---'\____// .' \| |// `.// / \||| : |||// \// / _||||| -:- |||||- \// | | \\ - /// | |// | \_| ''\---/'' | |// \ .-\__ `-` ___/-. /// ___`. .' /--.--\ `. . __// ."" '< `.___\_<|>_/___.' >'"".// | | : `- \`.;`\ _ /`;.`/ - ` : | |// \ \ `-. \_ __\ /__ _/ .-` / /// ======`-.____`-.___\_____/___.-`____.-'======// `=---='// ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^// 佛祖保佑 永无BUG#include #include