对于根节点 $u$ , 假设其有 $p$ 棵子树,每个子树 $i$ 的大小为 $sz[i]$ ,则判断割点的答案统计应为:
$$ \begin {equation} ans = ans + \sum \limits_{i=1}^{p} {sz[i] * (n - sz[i])} \tag {1} \end {equation} $$ 外层对这个根结点答案统计的与求和项有关的项为: $$ \begin {equation} ans = ans + (1 + \sum \limits_{i=1}^{p} {sz[i]}) * (n - 1 - \sum \limits_{i=1}^{p} {sz[i]}) \tag {2} \end {equation} $$ 当判断割点的行放到 ```if(u != 1 || flag > 1)``` 下( ```if``` 里面时)内层 sum 统计会少一个 $sz[j]$ , ans[1] 统计也会少,此时计算统计少了之后的 $(1) - (2)$ 发现取等条件为
小学数学来了。
comment 评论区
star_outline 咱快来抢个沙发吧!