参加市赛,看到一道题:
一棵 nnn 个节点的树,树上所有节点的度数总和是()。
这篇博客说,树中一个结点的孩子个数称为该结点的度。但根据 OI-Wiki 上的这个页面,无根树属于无向图,而有根树则是无根树+指定根结点。
我认为,既然无根树是无向图,那么根据握手定理,结点的度数和就应当为 2n−22n-22n−2。而有根树指定的根不影响图的有向/无向与度数,所以题目答案应为 2n−22n-22n−2。
求本题答案和依据。