【多校】H. Playf and Tree

【多校】H. Playf and Tree

H. Playf and Tree

一道比较基础的期望加树的遍历。对于操作次数的期望便是所有的点被直接操作的概率相加。

对于一个节点 ，它是确定的一定要被删除的，但是它删除的方式有两种，即要么是删除了它的一个祖先节点，要么是直接删除它自己 。直接删除的概率是它的深度的倒数。那么考虑所有点，它们被直接删除的概率都是其深度的倒数 ，那么在每个点上需要花费一次操作的概率也是如此，所以操作次数期望是所有深度倒数之和。 一次dfs即可求出答案。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<math.h>
#include <stack>
#include<map>
#include<stdlib.h>
#include<queue>
#define LL long long
using namespace std;
const int N=4e5+10;
struct edge{int nxt;int to;
}e[N];
int head[N],cnt=0,n;
int vis[N];
double ans=0;
void addedge(int u,int v){e[++cnt].nxt=head[u];e[cnt].to=v;head[u]=cnt;
}
void dfs(int x,double d){ans+=1.0/d;vis[x]=1;for (int i=head[x]; i!=0; i=e[i].nxt){if(vis[e[i].to]==0){dfs(e[i].to,d+1);}}
}
int main(){cin>>n;for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);addedge(x,y);addedge(y,x);}dfs(1,1.0);printf("%.9lf",ans);return 0;
}