[cf674E]Bear and Destroying Subtrees

令$f_{i,j}$表示以$i$为根的子树中，深度小于等于$j$的概率，那么$ans_{i}=\sum_{j=1}^{dep}(f_{i,j}-f_{i,j-1})j$

大约来估计一下$f_{i,j}$的大小，较坏情况下是$\lfloor\frac{n-1}{j}\rfloor$个深度为$j$的节点（若选择有公共部分，虽然会增加节点数但并实际边的数量减少），即可以认为$f_{i,j}\ge (1-\frac{1}{2^{j}})^{\lfloor\frac{n-1}{j}\rfloor}$

其在$j\ge 60$时，可以认为$f_{i,j}=1$，代入$ans_{i}$的式子即$j>60$的部分不需要计算

因此此时状态数为$o(Dn)$（其中$D=60$），接下来考虑如何维护

如果对其暴力dp，转移为$f_{i,j}=\frac{1}{2}f_{i,j}(1+f_{son,j-1})$，那么当插入节点的$k$，显然会修改$f_{fa_{k},0}$、$f_{fa_{fa_{k}},1}$等位置，因此插入复杂度为$o(D)$，查询时对该位置$f$求和同样为$o(D)$

总复杂度为$o(Dn)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 500005

 4 #define D 50

 5 vector<int>v;

 6 int V,n,p,x,fa[N];

 7 double ans,f[N][D+5];

 8 void New(int k){

 9     fa[++V]=k;

10     for(int i=0;i<=D;i++)f[V][i]=1;

11 }

12 int main(){

13     scanf("%d",&n);

14     New(0);

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

16         scanf("%d%d",&p,&x);

17         if (p==1){

18             New(x);

19             for(int j=1,k=x;(j<=D)&&(k);j++,k=fa[k])v.push_back(k);

20             while (v.size()){

21                 f[fa[v.back()]][v.size()]/=1+f[v.back()][(int)v.size()-1];

22                 v.pop_back();

23             }

24             f[x][0]/=2;

25             for(int j=1,k=x;(j<=D)&&(k);j++,k=fa[k])f[fa[k]][j]*=1+f[k][j-1];

26         }

27         else{

28             ans=0;

29             for(int j=1;j<=D;j++)ans+=(f[x][j]-f[x][j-1])*j;

30             printf("%.9f\n",ans);

31         }

32     }

33 }

巴特西

[cf674E]Bear and Destroying Subtrees

最新文章

热门文章