題目大意：一顆樹，給定每個點消失的概率，求出連通塊的期望值。要求支持修改消失概率的操作并且給出每次修改過后的期望值。注意被破壞的點不能算入連通塊中。

數據范圍，時限1S。

傳送門?D. Interstellar battle

?

我們考慮做有根樹的DP。設1為根。

我們設為v節點消失的概率，設分別表示v節點被破壞/沒被破壞時的連通塊期望值。

解釋一下f[v][1]的轉移方程：因為如果v節點沒有被破壞，并且兒子節點sn也沒有被破壞，那么連通塊的個數會減少，減少的數量就是sn所在的連通塊的期望，也就是。

當然我們不可能每次詢問了就DFS一遍計算，所以我們需要再研究一下遞推式。

我們先只考慮4號點對答案的貢獻。我么按照遞推式模擬一遍。

最后答案就是，也就是。推廣到一般情況：v對答案的貢獻就是，特別地，設（0是1的父親）。

知道這個結論過后維護起來就特別方便了。我們記。修改一個點的概率時就相應地修改值就行了（具體見代碼）。

代碼：

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> #include<set> #include<map> #include<vector> #include<ctime> #define ll long long #define N 100005using namespace std; inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}int n,m; double p[N]; struct load {int to,next;}s[N<<1]; int h[N],cnt; void add(int i,int j) {s[++cnt]=(load) {j,h[i]};h[i]=cnt;} int fa[N]; double sum[N]; void dfs(int v,int fr) {for(int i=h[v];i;i=s[i].next) {int to=s[i].to;if(to==fr) continue ;fa[to]=v;dfs(to,v);sum[v]+=(1-p[to]);} } double ans,c; int main() {n=Get();for(int i=1;i<=n;i++) scanf("%lf",&p[i]);p[0]=1;int a,b;for(int i=1;i<n;i++) {a=Get()+1,b=Get()+1;add(a,b),add(b,a);}dfs(1,0);for(int i=1;i<=n;i++) {ans+=p[fa[i]]*(1-p[i]);}m=Get();while(m--) {a=Get()+1;scanf("%lf",&c);ans-=p[fa[a]]*(1-p[a]);ans-=sum[a]*p[a];sum[fa[a]]-=1-p[a];p[a]=c;ans+=p[fa[a]]*(1-p[a]);ans+=sum[a]*p[a];sum[fa[a]]+=1-p[a];cout<<ans<<"\n";}return 0; }

?

然而，總覺得我的做法太不清真了。網上一搜題解，才發現了自己的naive。原來期望是可以分開計算的，也就是說可以分別算出每一對節點對答案的貢獻在加起來。然后公式基本相同的。

?

?

轉載于:https://www.cnblogs.com/hchhch233/p/9735814.html

總結

以上是生活随笔為你收集整理的codeforces 1045 D. Interstellar battle的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。