codeforces 696B Puzzles 树形概率计算

题意：给一棵有根树，从根节点深搜，每次随机走，问每个点的dfs序的期望是多少

分析：对于每一个点，它的所有祖先节点dfs序肯定在它之前，它所在的子树的节点一定在它后面，

剩下的是既不是子树又不是祖先的节点，可能在它之前，也可能在以后，这里面每个点在它之前的概率为0.5

也就是针对当前点，课变序列式呈对称态势的，所以最终期望是在中间

即：ret[u]=(n-son[u]-ancestor[u])/2+depth[u];这里的son[u]包括u

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <map>

#include <queue>

#include <vector>

using namespace std;

typedef long long LL;

const int N  = 1e5+;

const int INF = 0x3f3f3f3f;

const LL mod = 1e9+;

typedef pair<int ,int >pii;

struct Edge{

  int v,next;

}edge[N<<];

int head[N],tot,n,dep[N],son[N];

void add(int u,int v){

  edge[tot].v=v;

  edge[tot].next=head[u];

  head[u]=tot++;

}

double ret[N];

void dfs(int u,int f){

  son[u]=;dep[u]=dep[f]+;

  for(int i=head[u];~i;i=edge[i].next){

    int v=edge[i].v;

    dfs(v,u);

    son[u]+=son[v];

  }

  ret[u]=1.0*(n-dep[u]+-son[u])/2.0+dep[u];

}

int main(){

  scanf("%d",&n);

  memset(head,-,sizeof(head));

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

    int u;scanf("%d",&u);

    add(u,i);

  }

  dfs(,);

  for(int i=;i<n;++i)

    printf("%.1f ",ret[i]);

  printf("%.1f\n",ret[n]);

  return ;

}

巴特西

codeforces 696B Puzzles 树形概率计算

最新文章

热门文章