number of connected induced subgraph in a tree
Let $T$ be a tree rooted at $r$. Let the children of $r$ be $r_1,\ldots,r_\ell$, and let the corresponding subtrees be $T_1,\ldots,T_\ell$.

Consider a connected induced subgraph of $T$. There are two cases:


The subgraph doesn't contain $r$. In this case, the subgraph is a connected induced subgraph of some $T_i$.
The subgraph contains $r$. In this case, for each $i$, either the subgraph contains no vertices of $T_i$, or its intersection with $T_i$ is a connected induced subgraph of $T_i$ containing $r_i$.


Let us denote the number of subgraphs of the first type by $A(T)$, and those of the second type by $B(T)$. You are interested in $A(T) + B(T)$. The description above translates to the following recurrences:
$$
\begin{align}
A(T) &amp;= \sum_{i=1}^\ell (A(T_i) + B(T_i)) \\
B(T) &amp;= \prod_{i=1}^\ell (1 + B(T_i))
\end{align}
$$
Using this, you can calculate the number of connected induced subgraphs of a tree in linear time (ignoring the cost of arithmetic).