Aquacolor

Aquacolor



P3469的小问题证明

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


对于根节点 $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 评论区

添加新评论

face表情



  • ©2026 bilibili.com

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


star_outline 咱快来抢个沙发吧!




©2026 Aquacolor

Theme Romanticism2.2 by Akashi
Powered by Typecho