维护区间颜色数的一个较常用方法是说我维护某颜色最后一个出现的点在哪里,比如 HH 的项链和采花。
在一棵树上的时候,我们如果是信息是维护到一个点上,那么我们可以考虑dsu on tree,如果是说维护比如叶子到某一个点的颜色数,那么我们可以维护某一个颜色最靠上的一个点在哪里,然后 dfs 回退时,我们对当前子树做颜色加一,对子树内和跟颜色一样的子树做减一。这个可以详见这个。
维护区间颜色数的一个较常用方法是说我维护某颜色最后一个出现的点在哪里,比如 HH 的项链和采花。
在一棵树上的时候,我们如果是信息是维护到一个点上,那么我们可以考虑dsu on tree,如果是说维护比如叶子到某一个点的颜色数,那么我们可以维护某一个颜色最靠上的一个点在哪里,然后 dfs 回退时,我们对当前子树做颜色加一,对子树内和跟颜色一样的子树做减一。这个可以详见这个。