Enumeration of subtrees of trees

Let $T$ be a weighted tree. The weight of a subtree $T_1$ of $T$ is defined as the product of weights of vertices and edges of $T_1$. We obtain a linear-time algorithm to count the sum of weights of subtrees of $T$. As applications, we characterize the tree with the diameter at least $d$, which has the maximum number of subtrees, and we characterize the tree with the maximum degree at least $Δ$, which has the minimum number of subtrees.

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.