Problem Puzzles
题目大意
给一棵树，dfs时随机等概率选择走子树，求期望时间戳。
Solution
一个非常简单的树形dp?期望dp。推导出来转移式就非常简单了。
在经过分析以后，我们发现期望时间戳其实只需要考虑自己父亲下来（步数加一）&从兄弟回来两种可能。
设size[i]为i节点子树大小（包括自身）
对于兄弟的情况，i节点的一个兄弟有1/2的可能已经被遍历完毕了，也就是步数加size该兄弟。
于是设ans[i]为到达i点的期望值，则
ans[i]=ans[Father i]+1.0+(size[Father i]-size[i]-1)*1/2
首先我们先进行一遍dfs，求出所有节点的size，
然后再次dfs，算出ans，即可。具体详见代码。
AC Code
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct edge{
int next,to;
}e[];
int h[],size[],n,x,tot=;
double ans[];
int insr(int u,int v){
e[++tot].to=u;e[tot].next=h[v];h[v]=tot;
e[++tot].to=v;e[tot].next=h[u];h[u]=tot;
}
void dfssize(int x,int last){
size[x]=;
for(int i=h[x];~i;i=e[i].next){
if(e[i].to!=last){
dfssize(e[i].to,x);
size[x]+=size[e[i].to];
}
}
}
void calcans(int x,int last){
ans[x]=(x==)?1.0:ans[last]+1.0+0.5*(size[last]-size[x]-);
for(int i=h[x];~i;i=e[i].next)
if(e[i].to!=last)calcans(e[i].to,x);
}
int main(){
// freopen("cf697d.in","r",stdin);
memset(h,-,sizeof(h));
scanf("%d",&n);
ans[]=1.0;
for(int i=;i<=n;i++){
scanf("%d",&x);
insr(x,i);
}
dfssize(,);
calcans(,);
for(int i=;i<=n;i++)printf("%.2lf ",ans[i]);
}