srm683专题

TopCoder srm683 div2 1000

已经弱到去div2混了…… 题意:给一棵无根树,计算它的所有子树的大小的和。 这个问题转化为统计每个节点的“贡献”,即它在所有可能的子树中出现了多少次。还是先拿有根树来考虑,假设我们已经计算出了树t所有节点的“贡献”,如果在t中的某个叶子v上,连接一棵新的子树t’会怎么样呢?这样一来,v的贡献会将会被乘上“子树t’的树根的贡献+1”。于是,我们可以通过dfs,计算出以每个节点为根的子树中,该节