Аа )) Про неё там хорошо написал adaptatron в коментах: https://cfstep.com/codeforces/contests/contest-1929/problem-d/hints/

Привет, задачу решить то я вчера решил

Трудно объяснить своё решение) Особенно на моменте когда я начал уже писать коммент, а потом понял что мой коммент противоречит моему же решению

Так что давай ещё раз, по порядку:

П.с. дальше в тексте я закрашенной вершиной называю вершину, принадлежащую множеству.

Рассмотрим некую вершину U, и скажем, что она принадлежит множеству. Очевидно, что тогда у нас не могут одновременно существовать закрашенные вершины и в её поддереве, и снаружи от него.

Рассмотрим первый случай (поддерево)

Пусть dp[v] обозначает количество способов закрасить вершины в поддереве v (включая v) так, чтоб ни одна закрашенная вершина не являлась предком другой закрашенной вершины (не закрасить ни одну вершину так же считается подходящим способом). (Очевидно, dp[v] для v, являющегося листом, равен 2: либо мы красим V, либо нет.) Легко увидеть что dp[u] = (произведение(dp[v]) + 1) по всем её детям v (+1 т.к. мы можем не закрасить ни одну вершину кроме u, во всех остальных случаях, если хоть одна вершина в поддерве закрашена, u не может быть закрашен тоже), т.е. дп считается одним обходом в глубину.

Затем, если мы закрасили вершину U, то: если в поддереве как минимум двух её детей v1 и v2 существует по хотя бы одной закрашенной вершине (x1 и x2), то путь из x1 в x2 будет содержать U -> 3 закрашеные вершины <=> противоречие. Значит ans += dp[v] по всем детям v вершины u. (Именно такая формулировка дп нужна потому, что, если для какого то v в его поддереве закрашены 2 вершины так, что одна является предком другой, то u будет являться предком первой и путь из u в нижнюю будет содержать 3 покрашенные вершины)

Дополнительно: если U имеет хотя бы одного ребёнка, то т.к. все dp[v] включают и пустое множество, то мы посчитаем случай когда только U закрашен и все остальные — нет, ровно (количество детей U)+1 раз. Соответственно из ответа надо вычесть (количество детей U).

Теперь, прежде чем перейти ко 2 случаю (вершины закрашены только вне поддерева U), давай лучше рассмотрим случай когда мы закрасили какое то подмножество вершин поддерева u (так чтоб ни одна закрашенная вершина не являлась предком другой), но не закрасили сам u.

У нас могут случиться 3 варианта:

1) ни одна вершина вне поддерева u не закрашена. В таком случае количество расскрасок, удовлетворяющих этому условию считать не надо, т.к. позже оно будет посчитано в каком нибудь из предков u (пример: пусть во всём дереве только какие то вершины в поддереве u покрашены. Тогда для par[u] также верно что только какие то вершины в его поддереве покрашены, т.е. кол-во раскрасок для u будет включено в кол-во расскрасок для p[u] а значит во избежание пересчёта его добавлять не надо)

2) закрашен какой то из предков u. В таком случае количество раскрасок будет включено в dp[предка].

3) закрашена какая то вершина вне поддерева u, не являющаяся предком u (пусть эта вершина — v). Тогда количество раскрасок будет включено в количество раскрасок для поддерева lca(u,v), т.е. опять же, для u, не являющегося корнем, включать это в ответ не нужно.

Теперь можем увидеть что "Закрашена U, и какое то подмножество вершин вне поддерева U" будет посчитано либо случаем (1), либо одним из трех выше описанных случаев (которые все сводятся к одному — количеству способов закрасить подмножество всех вершин дерева кроме корня так, чтобы ни одна закрашенная вершина не была предком другой, что, как мы помним = произведение(dp[v]) по всем детям v корня (заметим что без +1 здесь, т.к. мы не закрашиваем сам корень)

Отсюда можем вывести, что ответ = сумма значений, посчитанных в (1) + произведение(dp[v]) детей корня. Заметим, что "произведение" равно ничему иному, как dp[корень]-1 :)

Т.е. получается ответ выходит sum(dp[i]) — 1 — sum(количество детей i) = sum(dp[i]) — 1 — (n-1)= sum(dp[i])-n

Ну и обрати внимание что, оказывается, мы случай, где только корень закрашен и остальные — нет, никак не рассмотрели (т.к. мы вычли (количество детей корня) из ответа), соответственно надо добавить к ответу 1

Т.е. ответ = $\sum$dp[i] — n + 1.

На этом всё)