codeforces 1045 D. Interstellar battle

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

數據范圍，時限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。原來期望是可以分開計算的，也就是說可以分別算出每一對節點對答案的貢獻在加起來。然后公式基本相同的。

?

?