一种$\mathcal{O}(n+m\log n\log_{B}n)$的做法
数据量只有$n\le 10^5$，考虑树链剖分后分层bitset维护全局节点颜色，对于一个节点$v$，在bitset中我们用$b[dfn[v]]=1$表示它是黑色，修改就是对第$v$位异或1，然后在依次修改每一层，对于一条重链$[l,r]$，dfn在其区间连续且递增，查询就转换为了找到区间内最左侧的1的下标。然后用分层bitset维护后继，更新答案，不断跳链直到为空，这里$B$取64。
QOJ.ac
QOJ
Discussion #3196 for Problem #18806. 트리와 쿼리 3
Type: Editorial
Status: Open
Posted by: KomariChika
Posted at:
Last updated:
New Editorial for Problem #18806
Comments
No comments yet.