题解

思路

任意时刻的颜色只由最近一次操作 1 给出的深度阈值决定。问题因此变成：查询一个子树中深度不小于当前阈值的结点数。

做法

小规模可在每次询问时直接扫描子树。若树是从根 1 开始的链，结点 $x$ 的子树为 $x,x+1,\ldots,n$，可直接用深度区间长度计算。

满分做法先迭代 DFS，求出每个结点的进入时间 tin、离开时间 tout 和深度。子树恰对应 DFS 序的连续区间。按 DFS 序建立深度值的持久化频率线段树，版本 $i$ 记录前 $i$ 个结点的深度。两个版本相减即可在 $O(\log n)$ 内求出子树区间中深度小于阈值的结点数，再用子树大小减去它。

正确性证明

操作 1 会完全覆盖此前颜色，所以当前黄色结点集合始终恰为所有深度不小于阈值的结点。DFS 序把任意子树映射为且仅映射为区间 $[tin_x,tout_x]$。持久化线段树的版本差精确统计该区间内各深度出现次数，因此“子树大小减去深度小于阈值的数量”恰为黄色结点数。

复杂度

预处理时间与空间均为 $O(n\log n)$；每次染色为 $O(1)$，每次询问为 $O(\log n)$。