2018.09.09 codeforces280C. Game on Tree(예상 dp)

전송문 기대 dp 고전 문제.분명히 점마다 검게 물든 기대 걸음수만 계산할 수 있다.점 i가 검게 물들기를 기대하는 것은 1/(i 이 체인의 노드 수) 1/(i 이 체인의 노드 수) 이다. 그래서 완성되었다.코드:

#include
#define N 100005
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
int first[N],n,cnt,dep[N];
double ans=0;
struct edge{int v,next;}e[N<<1];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline void dfs(int p,int fa){
    for(int i=first[p];i;i=e[i].next){
        int v=e[i].v;
        if(v==fa)continue;
        dep[v]=dep[p]+1,dfs(v,p);
    }
}
int main(){
    n=read();
    for(int i=1;iint u=read(),v=read();
        add(u,v),add(v,u);
    }
    dep[1]=1,dfs(1,1);
    for(int i=1;i<=n;++i)ans+=1.0/(1.0*dep[i]);
    printf("%.20lf",ans);
    return 0;
}