Description：

给一棵树，每个点受到攻击有 $p_i$ 的概率沦陷，求每次打击过后联通块个数的期望，支持修改点的概率。

$1\leqslant n \leqslant10^5$

Solution：

对于一棵树，它的联通块个数 $=$ 点数 $-$ 边数。原因是每加一条边联通块个数减一。

所以我们要求的就是 $E(V_G-E_G)$ ，由期望的线性性可得 $E(V_G-E_G)=E(V_G)-E(E_G)$ ： $$ E(V_G)=\sum_{i=1}^n1\times (1-p[i]) $$

$$ E(E_G)=\sum_{(i,j)\in E_G}1\times(1-p[i])\times (1-p[j]) $$

点的问题很容易维护，问题是边，如果是一个菊花图的话一个点会有 $O(n)$ 条边和他相连，那么如果不停修改这个点，每次暴力修改周围边的期望的话就被卡成了 $O(n^2)$ 。

另一个 $O(n^2)$ 的做法是记一下和每个点相连的点的概率和，每次修改时边的贡献很好计算，但是修改一个点又要更新周围一圈点的和。

考虑综合一下两种做法，在树上有一个重要的性质，就是每个点只有一个父亲，于是可以像 $\text{codeforces trourist}​$ 那题一样考虑把一些信息放到父节点上来做，设： $$ f[k]=\sum_{i\ is\ a\ child\ of\ k}(1-p[i]) $$ 那么有： $$ E(E_G)=\sum_{i=1}^n(1-p[i])\times f[i] $$ 每条边都被不多不少在父节点那里计算了一次，每次修改一个点的概率，只有 $p[i]$ 和 $f(fa[i])$ 的值会改变，这就非常好维护了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

double p[MAXN];

int fa[MAXN];

double f[MAXN];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

void dfs(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa[k])continue;

		fa[e[i].to] = k;

		dfs(e[i].to);

		f[k] += p[e[i].to];

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%lf",&p[i]);

	for(int i = 1;i <= n;++i)p[i] = 1.0 - p[i];

	p[0] = 0;

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);++a;++b;

		add(a,b);

	}

	dfs(1);

	double ans = 0;

	for(int i = 1;i <= n;++i)

	{

		ans += p[i] - p[i] * f[i];

	}

	scanf("%d",&m);

	int x;double y;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%lf",&x,&y);++x;y = 1.0 - y;

		ans = ans - p[x] + y;

		ans += p[x] * f[x] - y * f[x];

		ans += p[fa[x]] * f[fa[x]];

		f[fa[x]] = f[fa[x]] - p[x] + y;

		ans -= p[fa[x]] * f[fa[x]];

		p[x] = y;

		printf("%.6lf\n",ans);

	}

	return 0;

}