codeforces 1045 D. Interstellar battle

题目大意：一颗树，给定每个点消失的概率，求出连通块的期望值。要求支持修改消失概率的操作并且给出每次修改过后的期望值。注意被破坏的点不能算入连通块中。

数据范围 $10^{5}$ ，时限1S。

传送门 D. Interstellar battle

我们考虑做有根树的DP。设1为根。

我们设 $p[v]$ 为v节点消失的概率，设 $f[v][0],f[v][1]$ 分别表示v节点被破坏/没被破坏时的连通块期望值。

$f[v][0]=p[v]\cdot \sum (f[sn][0]+f[sn][1])$

$f[v][1]=(1-p[v])\cdot (1+\sum (f[sn][0]+f[sn][1]-(1-p[sn])))$

解释一下f[v][1]的转移方程：因为如果v节点没有被破坏，并且儿子节点sn也没有被破坏，那么连通块的个数会减少，减少的数量就是sn所在的连通块的期望，也就是 $1-p[sn]$ 。

当然我们不可能每次询问了就DFS一遍计算，所以我们需要再研究一下递推式。

我们先只考虑4号点对答案的贡献。我么按照递推式模拟一遍。

最后答案就是 $f[1][0]+f[1][1]$ ，也就是 $p[3]*(1-p[4])$ 。推广到一般情况：v对答案的贡献就是 $p[fa[v]]*(1-p[v])$ ，特别地，设 $p[0]=1$ （0是1的父亲）。

知道这个结论过后维护起来就特别方便了。我们记 $sum[v]=\sum (1-p[sn])$ 。修改一个点的概率时就相应地修改值就行了（具体见代码）。

代码：

#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 100005

using 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。原来期望是可以分开计算的，也就是说可以分别算出每一对节点对答案的贡献在加起来。然后公式基本相同的。

巴特西

codeforces 1045 D. Interstellar battle

最新文章

热门文章