[Codeforces1046D][BFS序][树状数组]Interstellar battle

翻译

给出一棵树以及树上的点消失的概率
Q次修改
每次修改一个点消失的概率
问每次修改之后当前树剩下的连通块个数的期望
Q<=200000 N<=100000

题解

通过这题gay到了一个新姿势：
树上连通块个数=点数-边数
相当于动态维护一个$E(V?E)$
根据期望的线性性，上式可以写为$E(V)?E(E)$
可以先将消失的概率转化为存在的概率 记为$cal[i]$
显然$E(V)=\sum cal[i]$
下来考虑动态维护$E(E)$
我们考虑一条边存在的期望 当且仅当它所连接的两个点均没消失 记这两点为$(u,v)$
则一条边$K$存在的期望为$E(u)?E(v)$
相当于维护一个$\sum E(u)?E(v)$
考虑一个点被修改的影响
只会影响与他相连的边
这些边可以分为两类 一类连向儿子一类连向父亲虽然父亲只有一条边
父亲这条边的贡献可以暴力改掉
搞出BFS序 显然一个点的所有儿子的BFS序是连续的
树状数组乱撸

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #define LL long long #define mp(x,y) make_pair(x,y) using namespace std; inline int read() {
     int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
     if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
     x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
     if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
     write(x);printf(" ");} struct node{
     int x,y,next;}a[210000];int len,last[110000]; void ins(int x,int y){
     len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;} queue<int> li; int fa[110000]; void pre_tree_node(int x) {
     for(int k=last[x];k;k=a[k].next)if(a[k].y!=fa[x])fa[a[k].y]=x,pre_tree_node(a[k].y); } int in[110000],ot[110000],deg[110000],bfn; int fir[110000]; void init_BFS() {
     li.push(1);in[1]=++bfn;while(!li.empty()){
     int x=li.front();fir[x]=bfn;for(int k=last[x];k;k=a[k].next)if(a[k].y!=fa[x]){
     int y=a[k].y;in[y]=++bfn;li.push(y); }li.pop();ot[x]=bfn;} } double s[110000]; int n,T; int lowbit(int x){
     return x&-x;} void change(int x,double c){
     for(int i=x;i<=n;i+=lowbit(i))s[i]+=c;} double findsum(int x){
     double ret=0;for(int i=x;i>=1;i-=lowbit(i))ret+=s[i];return ret;} double cal[110000]; int main() {
     n=read();for(int i=1;i<=n;i++)scanf("%lf",&cal[i]),cal[i]=1.0-cal[i];for(int i=1;i<n;i++){
     int x=read(),y=read();x++;y++;ins(x,y);ins(y,x);}pre_tree_node(1);init_BFS();for(int i=1;i<=n;i++)change(in[i],cal[i]);T=read();double s1=0,s2=0;for(int i=1;i<=n;i++)s1+=cal[i];for(int i=1;i<=n;i++){
     double S=findsum(ot[i])-findsum(fir[i]);s2+=cal[i]*S;}//printf("%.5lf\n",s1-s2);while(T--){
     int x=read();double c;scanf("%lf",&c);c=1-c;x++;s1-=cal[x];s1+=c;double S=findsum(ot[x])-findsum(fir[x]);s2-=cal[x]*S;s2+=c*S;s2-=cal[x]*cal[fa[x]];s2+=c*cal[fa[x]];change(in[x],-cal[x]+c);cal[x]=c;printf("%.5lf\n",s1-s2);}return 0; }