树上经典的 trick:判断一个链上不同颜色的个数。
我们要知道树上一个链上不同的颜色个数。
\(n=2*10^5\)
考虑记录数组\(lst\),\(lst_i\)代表节点\(i\)的祖先中,距离节点\(i\)最近且颜色和他相同的祖先的\(dfs\)序。
然后使用线段树+dfn查询这个链上\(lst\)小于链顶dfn序的节点的个数
我们要知道树上一个链上不同的颜色个数。
\(n=2*10^5\)
考虑记录数组\(lst\),\(lst_i\)代表节点\(i\)的祖先中,距离节点\(i\)最近且颜色和他相同的祖先的\(dfs\)序。
然后使用线段树+dfn查询这个链上\(lst\)小于链顶dfn序的节点的个数