Tag Info

Let's build some recursive function. We start picking any vertex of the tree $T$ and call it $R$ as root. If $R$ was removed, you would get a forest of several sub-trees. Every subtree $T_k$ has a vertex $k$ connected to $R$ in $T$. Now there are 3 types of paths contributing to the sum of cost of paths $N(R)$: $I(R)$, the cost of all inner paths of the ...