[ABC340G] Leaf Color

Richard_Whr · 2024-02-13 22:10:20 · 题解

简要题意：

给你一颗树，每个点有颜色。问你有多少个连通块，度为 1 的节点的颜色都相同。

首先考虑 O(n^2) 的做法：

设 f[u][x] 表示以 u 为跟的子树中，必选根有多少种方案，使得他作为父亲的子树是合法的。

这样设计的原因是为了方便转移，使得状态具有延续性。

初始 f[u][x]=1，表示只选根，但很明显对于 color[u] \neq x 是不合法的，为了方便，我们最后减去即可，这里先假装合法。

对于每一颗子树以 v 为根，都有选和不选两种方案：

• 不选：就是 f[u][x]；

• 选：原来的每一种方案和这颗子树中的每个方案都可以配对，因此是乘法原理：f[u][x] \times f[v][x]；

因此有：

最后记得将某些不合法情况减去。

不过我们可以发现，真正统计答案的时候，f 内的方案不一定都是合法方案，分情况讨论：

• 当该点颜色就是 x 的时候，以 u 为根的连通块内的所有合法方案数就是 f[u][x]。

• 当该点颜色不是 x 的时候，以 u 为根的连通块内所有的合法方案，要减掉我们单独选了某个子树的情况，因为这样根的度为 1。

对于第二种情况，我们利用辅助数组 g

令：

此时我们就可以统计答案了，对于每个节点，我们统计连通块以他为根的答案（他的深度最小）。

此时需要敏感的点来了，我们发现对于一种颜色，真正就有价值的点并不多，很多转移都是无效而浪费时间的。

考虑建立虚树，这样我们将每种颜色单独抠出来做，即可保证复杂度为 O(nlogn)

代码