The first step is how to deal with

Unable to parse markup [type=CF_TEX]

.Here we can use Stirling Number of the second kind. Let's define

Unable to parse markup [type=CF_TEX]

the number of ways to put

Unable to parse markup [type=CF_TEX]

different elements into

Unable to parse markup [type=CF_TEX]

sets and there are no empty set.Note that the all

Unable to parse markup [type=CF_TEX]

sets are the same.For example

Unable to parse markup [type=CF_TEX]

.The three ways are

Unable to parse markup [type=CF_TEX]

.So we have:

Unable to parse markup [type=CF_TEX]

How to proof it?

Unable to parse markup [type=CF_TEX]

is the number of ways to put

Unable to parse markup [type=CF_TEX]

different elements into

Unable to parse markup [type=CF_TEX]

different sets and empty sets are allowed.The other side of the equation means we select

Unable to parse markup [type=CF_TEX]

sets from

Unable to parse markup [type=CF_TEX]

sets and arrange them in

Unable to parse markup [type=CF_TEX]

different orders and put

Unable to parse markup [type=CF_TEX]

different elements in it. So the fomula in the statement becomes:

Unable to parse markup [type=CF_TEX]

Which equals to:

Unable to parse markup [type=CF_TEX]

For

Unable to parse markup [type=CF_TEX]

we can use the following

Unable to parse markup [type=CF_TEX]

DP to calculate all

Unable to parse markup [type=CF_TEX]

.

Unable to parse markup [type=CF_TEX]

Unable to parse markup [type=CF_TEX]

Which means we consider the

Unable to parse markup [type=CF_TEX]

sets.

For

Unable to parse markup [type=CF_TEX]

we use tree DP. Let's define

Unable to parse markup [type=CF_TEX]

the number of sets

Unable to parse markup [type=CF_TEX]

plus the number of some tricky situation(I'll show you what it is later) when we select

Unable to parse markup [type=CF_TEX]

edges in the subtree of node

Unable to parse markup [type=CF_TEX]

.In addition,there should exist a node

Unable to parse markup [type=CF_TEX]

for every selected edge

Unable to parse markup [type=CF_TEX]

that

Unable to parse markup [type=CF_TEX]

is in the subtree of

Unable to parse markup [type=CF_TEX]

.The initial value is:

Unable to parse markup [type=CF_TEX]

Means we can choose node

Unable to parse markup [type=CF_TEX]

or not. When we add an child

Unable to parse markup [type=CF_TEX]

of

Unable to parse markup [type=CF_TEX]

into our DP states we go through every possible

Unable to parse markup [type=CF_TEX]

and we select

Unable to parse markup [type=CF_TEX]

edges in the subtree of

Unable to parse markup [type=CF_TEX]

or we select

Unable to parse markup [type=CF_TEX]

edges in the subtree of

Unable to parse markup [type=CF_TEX]

and select edge

Unable to parse markup [type=CF_TEX]

.So we have:

Unable to parse markup [type=CF_TEX]

Where

Unable to parse markup [type=CF_TEX]

is the previous state without add informations of

Unable to parse markup [type=CF_TEX]

.Note that in order to hold "there should exist a node

Unable to parse markup [type=CF_TEX]

for every selected edge

Unable to parse markup [type=CF_TEX]

that

Unable to parse markup [type=CF_TEX]

is in the subtree of

Unable to parse markup [type=CF_TEX]

" we have to minus

Unable to parse markup [type=CF_TEX]

invalid state which is "select edge

Unable to parse markup [type=CF_TEX]

but select no node in the subtree of

Unable to parse markup [type=CF_TEX]

". And for answer,we have to know what are those tricky situation.For example,we only select nodes from one subtree of

Unable to parse markup [type=CF_TEX]

and some of the edges cannot be selected according to the defination of

Unable to parse markup [type=CF_TEX]

because none of their ancestors is selected.So we have to go through all the children of

Unable to parse markup [type=CF_TEX]

and minus them.Let's define

Unable to parse markup [type=CF_TEX]

be the number of sets

Unable to parse markup [type=CF_TEX]

when we select

Unable to parse markup [type=CF_TEX]

edges in the subtree of node

Unable to parse markup [type=CF_TEX]

.So we have:

Unable to parse markup [type=CF_TEX]

And now we finally have:

Unable to parse markup [type=CF_TEX]

The total complexity is

Unable to parse markup [type=CF_TEX]

. My code:https://codeforces.me/contest/1097/submission/48058882