51NOD1405 | Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

51NOD1405

链接

https://www.51nod.com/Challenge/Problem.html#!#problemId=1405

题意

        给n个节点的无根树，边权为1，求树上所有路径长度的和。

题解

        随便找个点作为根，树形dp出son[i]：子树i的节点的个数，再来一遍树形dp就可以求出以i为起点的所有路径长度的和。