题解 CF1045D 【Interstellar battle】

· · 题解

数据范围才1e5根号算法暴搞了事

本题题解

我们可以很显然的得出一个结论是剩下的联通块个数=幸存点数-两端点都幸存的边数目,显然这个式子两端同时取期望还是成立的

换句话说我们如果设w_{i}=1-p_{i}也就是i这个点存在的概率

那么我们要维护的式子就是

\sum_{i=1}^{n}w_{i}-\sum_{i=1}^{n-1}w_{u_{i}}w_{v_{i}}

其中u_{i},v_{i}表示第i条边连接的两个点

那么\sum_{i=1}^{n}w_{i}维护起来相当容易

关键是维护所有边的权值之和

那么我们考虑修改一个点u的时候,只有端点为u的边的权值会发生变化

而且更进一步的讲，如果我们知道了所有和u相连的点的权值之和的话,我们就可以处理答案了,假设所有和u相连的点的权值之和是sum的话,我们让答案减去旧的w_{u}×sum加上新的w_{u}×sum就行了

那么我们怎么求所有和u相连的点的权值之和呢？

显然不能每次粗暴的大力for一下，这样我们碰到菊花图就炸飞了

这张图是一个树，所以我们似乎有一些精妙的做法可以过掉这题？

好烦啊不想推式子……不如根号暴搞一发？

我们对于每条边(u,v)分类讨论,如果u的度数大于v就将这条边定向为u指向v，反之则令v指向u

那么现在我们在这张重定向的图中统计和一个点相连的所有点的点权和的时候 我们分为u指向的点和指向u的点这两种点进行计算

为了保证复杂度我们记sum_{u}表示所有指向u的点的点权和

那么我们此时查询所有和u相连的点权之和的时候就变得异常简单了我们先直接读取sum_{u}得到指向u的点的点权之和,之后大力for一遍出边计算u指向的点的点权

当我们修改u的点权的时候for一遍出边修改u指向点的sum值就行了

容易看出我们修改和查询的复杂度都是O(一个点的出度)的,我们可以证明的是这样建图每个点度数最坏是O(\sqrt{m})级别的,因此我们的算法复杂度就是O(Q\sqrt{N})的

实际情况下非构造数据基本跑不满

上代码~

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;const int N=1e5+10;typedef long long ll;typedef double db;
db p[N];vector <int> v[N];db sum[N];int d[N];int eu[N];int ev[N];int n;db ans;int q;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%lf",&p[i]),p[i]=1-p[i],ans+=p[i];
    for(int i=1;i<n;i++)
        scanf("%d%d",&eu[i],&ev[i]),d[eu[i]]++,d[ev[i]]++;
    for(int i=1;i<n;i++)//定向 
        if(d[eu[i]]<d[ev[i]])v[eu[i]].push_back(ev[i]),sum[ev[i]]+=p[eu[i]];
        else v[ev[i]].push_back(eu[i]),sum[eu[i]]+=p[ev[i]];
    for(int i=1;i<n;i++)ans-=p[eu[i]]*p[ev[i]];
    scanf("%d",&q);vector <int> :: iterator it;
    for(int i=1,u;i<=q;i++)//暴力 
    {
        db del=0;scanf("%d",&u);del=sum[u];
        for(it=v[u].begin();it!=v[u].end();++it)del+=p[*it],sum[*it]-=p[u];
        ans+=p[u]*del;ans-=p[u];scanf("%lf",&p[u]);p[u]=1-p[u];ans-=p[u]*del;ans+=p[u];
        for(it=v[u].begin();it!=v[u].end();++it)sum[*it]+=p[u];
        printf("%lf\n",ans);
    }return 0;
}