bzoj 3091 & Luogu P4842 城市旅行 题解

Description

题目链接Luogu darkbzoj

给定一个森林,初始形态是一棵以 $1$ 为根的树,要求进行以下操作。

  1. 连接 $x,y$
  2. 断开 $x,y$
  3. $x$ 到 $y$ 的路径上每个点权值加上 $d$
  4. 求在 $x$ 到 $y$ 的路径上任选 $2$ 个点之间路径上点的权值和的期望

对于 $100\%$ 的数据,满足 $1<=N<=50,000;1<=M<=50,000;1<=a_i<=10^6;1<=D<=100;1<=U,V<=N$。

Solution

对于有 $Link$ 与 $Cut$ 的动态树问题,考虑使用 $LCT$。

设这条路径是 $a_1,a_2,a_3,\dots,a_{sz}$,其中 $sz$ 是路径的长度。

对于每个点的期望,我们考虑路径上的每个点会被计算几次。

路径上的第 $i$ 个点权值为 $a_i$,显然当$1\leq l\leq i,i\leq r \leq sz$时会被计算到。($l,r$表示路径上选择的两个点)

那么这个点会被计算到 $i\times (sz-i+1)$ 次,所以产生的贡献就是 $i\times (sz-i+1)\times a_i$。

故易知期望值就是 $$\frac{\sum\limits_{i=1}^{sz}i\times (sz-i+1)\times a_i}{C_{sz+1}^2}$$

Q:为什么是 $C_{sz+1}^2$ 而不是 $C_{sz}^2$ 呢?

A:因为任选两个点可以是相同。

然后让我们来考虑维护这个又臭又长的答案。

首先考虑分母 $C_{sz+1}^2$,这个特别好维护,只需要维护下每个点的 $sz$ 即可,最后 $split$ 下就好了。

然后我们考虑分子如何维护,也就是说如何从左子树与右子树来得到这个答案。

我们设左子树的路径是 $a_1,a_2,\dots,a_{mid-1}$,路径长度是 $mid-1$。

然后,当前点的权值是 $a_{mid}$。

同理,右子树的路径是 $a_{mid+1},a_{mid+2},\dots,a_{sz}$,路径长度是 $sz-mid$

那么,当前点的应得答案就是 $\sum\limits_{i=1}^{sz}i\times(sz-i+1)\times a_i$

左子树的答案就是 $\sum\limits_{i=1}^{mid-1}i\times(mid-i)\times a_i$当前点的贡献是 $a_{mid}\times mid\times (sz-mid+1)$

右子树的答案就是 $\sum\limits_{i=mid+1}^{sz-mid}(i-mid)\times (sz-i+1)\times a_i$

然后你就会发现,如果把当前点应得的答案拆分下:

$$\sum\limits_{i=1}^{mid-1}i\times (sz-i+1)\times a_i + a_{mid}\times mid\times (sz-mid+1) \sum\limits_{i=mid+1}^{sz-mid}i\times (sz-i+1)\times a_i$$

然后将其与左右子树的答案作差可得:

$$\sum\limits_{i=1}^{mid-1}i\times (sz-mid+1)\times a_i + a_{mid}\times mid\times (sz-mid+1)+\sum\limits_{i=mid+1}^{sz-mid} mid\times (sz-i+1)\times a_i$$

此时,为了更佳的观赏效果,我们重新设一下。

设左子树的路径是 $b_1,b_2,\dots,b_{sz_b}$,其中 $sz_b$ 表示左子树的路径长度。

同理,我们设右子树的路径是 $c_1,c_2,\dots,c_{sz_c}$,其中 $sz_c$ 表示右子树的路径长度。

最后,设我们这个点的权值为 $a$。

那么其实差值就是:

$$(sz_c+1)\times \sum\limits_{i=1}^{sz_b}b_i\times i + a\times (sz_b+1)\times (sz_c+1)+ (sz_b+1)\times \sum\limits_{i=1}^{sz_c} (sz_c-i+1)\times c_i$$

所以,我们就可以维护下 $lsum=\sum\limits_{i=1}^{sz}i\times a_i,rsum=\sum\limits_{i=1}^{sz} (sz-i+1)\times a_i$ 以快速 $pushup$ 答案。

那么问题来了,我们如何维护 $lsum$ 与 $rsum$ 呢?

很显然,(其中 $s$ 表示所有 $a_i$ 的和)

$$lsum[x]=lsum[ls]+v[x]\times (sz[ls]+1)+lsum[rs]+s[rc]\times (sz[ls]+1)$$

$$rsum[x]=rsum[rs]+v[x]\times (sz[rs]+1)+rsum[ls]+s[ls]\times (sz[rs]+1)$$

简单的来说,思路就是从左右儿子继承并注意前面的系数即可。

好了,至此,我们已经完成了如何从左右儿子得到自己,现在我们要考虑操作 $3$ 带来的影响。

为了方便阅读,这里再次给出操作 $3$ 的概括:把$x$ 到 $y$ 的路径上每个点权值加上 $d$。

那么其实就是:

  • $s+=d\times sz$
  • $lsum+=\sum\limits_{i=1}^{sz}i\times d$ 即 $lsum+=\frac{sz\times (sz+1)}{2}\times d$
  • $rsum$ 与 $lsum$ 同理,$rsum+=\frac{sz\times(sz+1)}{2}\times d$
  • $ans+=\sum\limits_{i=1}^{sz}i\times (sz-i+1)\times d$ 即 $ans+=\frac{sz\times (sz+1)\times (sz+2)}{6}$

然后就完事了

Code

暂无评论

发送评论 编辑评论


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