高度由习惯堆积

分类 算法:DSU-ON-TREE 下的文章

February 17, 2019

CF570D Tree Requests

题目一棵以1为根的树,每个节点上都有1个字母,有m个询问。每次询问v对应的子树中,深度为h的这层节点的字母,能否打乱重排组成回文串。根的深度为1,每个点的深度为到根的距离。思路1(DSU)这应该是比较无脑的一种思路,开一个$cnt[M][i]$记录i这个颜色在某个深度出现了多少次,再开一个tmp记录对于这个深度,cnt是奇数的个数(如果在某个深度,奇数的个数是0或1,那么其就能组成回文串)