10.26 T3.蚊子(mosquito) (树形dp)
【題目描述】
作為一只明媚的兔子,要會疊被子,又得會打蚊子…
兔子住在兔子洞里.兔子洞可以看成是一棵無根樹,有n個洞穴,有n-1條通道連接著n個洞穴.
每天晚上,兔子會在1號洞穴里縮成一團(tuán),睡一覺.同時,蚊子大軍出動,去欺負(fù)兔子.
因?yàn)槲米尤硕鄤荼?所以它們分兵m*(m-1)路.m是整個兔子洞中只和一條通道相鄰的洞穴數(shù)目.任意兩個這樣的洞穴a,b之間(也就是任意兩個葉子節(jié)點(diǎn)之間)會有兩只蚊子,一只從a飛到b,一只從b飛到a.它們都沿著a到b的最短路徑移動.蚊子每秒鐘可以通過一條通道.所有蚊子都在0s時突然出現(xiàn)在起點(diǎn)并開始移動.每只蚊子在到達(dá)終點(diǎn)后的一瞬間都會突然消失.有些蚊子并不會經(jīng)過兔子所在的1號節(jié)點(diǎn),它們起到的是恐嚇作用.
又一次滿臉是包地醒來后,兔子忍無可忍了,于是它找到liu_runda讓liu_runda去打蚊子…liu_runda不知所措,于是去某寶搞了一個滅蚊器…這個滅蚊器被放在1號節(jié)點(diǎn).每個時刻,它都會工作一次,把和滅蚊器距離小于等于d范圍內(nèi)的蚊子全部殺死.(d=0時只能控制1號點(diǎn)一個位置)
遺憾的是,兔子洞尚未通電,兔子只能用愛發(fā)電.因此,每個時刻滅蚊器只有p/q的概率能夠正常工作.如果不能正常工作,那么蚊子將不受到任何影響.
滅蚊器無法影響出現(xiàn)之前和消失之后的蚊子.但在蚊子出現(xiàn)在起點(diǎn)和消失在終點(diǎn)的那個時刻,如果滅蚊器正常工作且蚊子在作用范圍內(nèi),這只蚊子仍會被殺死.
兔子對liu_runda的誠意表示懷疑…于是它讓liu_runda算出滅蚊器在一晚上期望能殺死多少蚊子.liu_runda當(dāng)然會算了,但是他想考考你.
因?yàn)橥米佑憛捫?shù),你需要輸出這個期望值模109+7后的結(jié)果.即:如果期望值可以表示成有理數(shù)a/b(a,b為整數(shù)),你需要輸出a*b-1 mod 1000000007(109+7)的值.
(如果你算錯了,就會被liu_runda拿去喂兔子,啊嗚~~)
【輸入格式】
第一行一個整數(shù)n,表示兔子洞中洞穴的個數(shù).洞穴編號為1到n的整數(shù).
接下來n-1行,每行兩個整數(shù)u,v,表示u和v兩個洞穴之間有一條通道.
接下來一行三個整數(shù)d,p,q,表示滅蚊器的作用范圍是d,每個時刻工作的概率是p/q.
【輸出格式】
一行一個整數(shù)ans,表示期望模109+7的值.
【樣例輸入】
3
1 2
1 3
1 1 2
【樣例輸出】
750000007
【樣例解釋】
共有2只蚊子,一只從2飛到3,一只從3飛到2.滅蚊器的作用范圍是1,那么三個點(diǎn)都在作用范圍內(nèi),每個蚊子會有三個時刻在作用范圍內(nèi),那么每只蚊子生還的概率都是1/8,經(jīng)過計(jì)算,我們期望能夠打死7/4只蚊子,說明liu_runda提供的滅蚊器是比較靠譜的.我們輸出7*4-1mod1000000007的值750000007.
【數(shù)據(jù)范圍】
記m為葉子節(jié)點(diǎn)的個數(shù).
對于第1個測試點(diǎn),n=300
對于第2,3個測試點(diǎn),n=3000
對于第4個測試點(diǎn),d=0,n=100000
對于第5個測試點(diǎn),p/q=1,n=100000
對于第6,7個測試點(diǎn)n=5000000,m<=500
對于第8,9,10個測試點(diǎn),n=5000000
對于所有測試點(diǎn),m < n<=5000000,0<=d<=n,1<=p<=q<=109+7保證1號節(jié)點(diǎn)至少和兩條通道相連.
分析:
考場上想的差不多了,但是就連部分分的碼量我都很崩潰
每只蚊子的貢獻(xiàn)是1-(1-p/q)^k(k是有效的時間)
我們可以先不管前面那個1,把后面的(1-p/q)^k的和求出來,最后用m*(m-1)減去那個和就可以了
一條路徑可以在LCA處拆成兩條
我們考慮如何求出以某個點(diǎn)為LCA的所有路徑的貢獻(xiàn)之和
一條路徑可以拆成兩部分,一部分是從一個葉節(jié)點(diǎn)走到LCA,另一部分是從LCA走到另一個葉節(jié)點(diǎn),把這兩部分看作兩條”半路徑”
記g[i]為以i為LCA的所有半路徑的貢獻(xiàn)之和
對于i子樹內(nèi)的每個葉節(jié)點(diǎn)x,g[i]+=(1-p/q)^k,k是x到i的半路徑上的被控制點(diǎn)的個數(shù)
g[i]可以通過O(n)樹形dp得到
接下來我們通過g[i]求出以每個點(diǎn)為LCA的路徑的貢獻(xiàn)之和
對于點(diǎn)x,考慮它的所有兒子,每一對兒子(u,v)的貢獻(xiàn)是g[u] * g[v] * (1-p/q)
注意,(u,v)和(v,u)都需要算一次
直接暴力枚舉每一對兒子會超時
我們通過乘法分配律可以用O(兒子個數(shù))的時間復(fù)雜度算出來
總的時間復(fù)雜度仍為O(n)
空間復(fù)雜度也為O(n)
總結(jié)
以上是生活随笔為你收集整理的10.26 T3.蚊子(mosquito) (树形dp)的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 入门matplotlib绘图【完整版】
- 下一篇: php 点号 的用法,基于php中ech