10 月 17 日 , 2026 10:09:53
每日学习(虚树边权和)

考虑树上任意 $k$ 个点 $a_1,a_2\cdots a_k$,包含他们的最小连通子树的边树(也即他们的虚树边权和)可以用如下方式求出:

考虑将 $k$ 个点按照 dfn 序从小到大排列为 $p_1,p_2\cdots p_k$,特别的,钦定 $p_{k+1}=p_1$,则虚树边权和等于 $\frac{\sum_{i=1}^k \text{dist}(p_i,p_{i+1})}{2}$,其中 $\text{dist}(i,j)$ 表示树上 $i,j$ 两点最短路径的边数。

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!