Автор задачи и разработчик: Николай Будин

В задаче было дано дерево, каждая вершина которого покрашена в один из $$$m$$$ цветов. Требовалось посчитать количество связных подграфов, которые содержат вершины всех цветов.

Для решения этой задачи, можно воспользоваться формулой включений-исключений. Переберем подмножество цветов $$$s$$$ и найдем количество связных подграфов, которые не содержат вершины, не принадлежащие множеству $$$s$$$. Пусть это количество равно $$$f(s)$$$. Тогда ответом является:

$$$$$$\sum_{s = 0}^{2^m - 1} f(s) \cdot (-1)^{m - |s|}$$$$$$

Чтобы лучше понять, почему эта формула работает, рассмотрим несколько слагаемых. Слагаемое $$$f(2^m - 1)$$$ это просто количество всех связных подграфов. Вычтем из них те, в которых нет цвета $$$x$$$, потому что они нам не подходят — для этого в сумме есть слагаемые $$$-f(2^m - 1 - 2^x)$$$. Однако, теперь мы дважды вычли подграфы, в которых нет ни цвета $$$x$$$, ни цвета $$$y$$$ ($$$x \neq y$$$). Прибавим их один раз — слагаемое $$$f(2^m - 1 - 2^x - 2^y)$$$. И так далее.

Теперь научимся вычислять $$$f(s)$$$. Оставим в дереве только вершины, цвет которых находится в множестве $$$s$$$. Ответом является сумма по всем компонентам связности количество различных связных подграфов в компоненте. Поэтому, осталось научиться считать количество связных подграфов в дереве. Это делается простой динамикой по поддеревьям. Значение $$$dp[v]$$$ равно количеству различных связных подграфов, лежащих в поддереве $$$v$$$ и содердащих $$$v$$$.