2018武大校赛.D. Who killed Cock Robin(树形dfs)

Who killed Cock Robin?

I, said the Sparrow, With my bow and arrow,I killed Cock Robin.

Who saw him die?

I, said the Fly.With my little eye,I saw him die.

Who caught his blood?

I, said the Fish,With my little dish,I caught his blood.

Who'll make his shroud?

I, said the Beetle,With my thread and needle,I'll make the shroud.    

.........

All the birds of the air

Fell a-sighing and a-sobbing.

When they heard the bell toll.

For poor Cock Robin.

March 26, 2018

Sparrows are a kind of gregarious animals,sometimes the relationship between them can be represented by a tree.

The Sparrow is for trial, at next bird assizes,we should select a connected subgraph from the whole tree of sparrows as trial objects.

Because the relationship between sparrows is too complex, so we want to leave this problem to you. And your task is to calculate how many different ways can we select a connected subgraph from the whole tree.