Aquacolor

Aquacolor



P3469的小问题证明

zcxsb · 2025-11-04 · 15浏览 · 未分类


对于根节点 $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)$ 发现取等条件为

$$ \sum \limits _ {i = 1} ^ {p} {sz[i]} + 1 = sz[j] \\ or \\ \sum \limits _ {i = 1} ^ {p} {sz[i]} + 1 = n $$ 其中 $\sum \limits _ {i = 1} ^ {p} {sz[i]}$ 是原来的和,易得下面那个等式成立,因此放在 `if` 内外都是无所谓的。

小学数学来了。





comment 评论区

添加新评论





  • ©2025 bilibili.com

textsms
内容不能为空
account_circle
昵称不能为空
email
邮件地址格式错误
web
beach_access
验证码不能为空
keyboard发表评论


star_outline 咱快来抢个沙发吧!




©2025 Aquacolor

鄂ICP备2024059763号-1

鄂公网安备42011102005556号



Theme Romanticism2.1 by Akashi
Powered by Typecho