【数学相关、规律】Codeforces 696B Puzzles

题目链接：

　　http://codeforces.com/problemset/problem/696/B

题目大意：

　　给一棵树，从根节点开始递归，time=1,每次递归等概率随机访问这个节点的子节点，走过不会再走，每访问到一个新节点time+1，求访问每个节点的时间的期望。

题目思路：

　　【数学规律】

　　这题其实是一道概率DP的题目，但是找规律后发现答案和当前结点的子树大小有关。

　　ans[v]=ans[u]+1+0.5*(child[u]-child[v]-1)，child为当前节点的子树大小。

  1 //
  2 //by coolxxx
  3 ////<bits/stdc++.h>
  4 #include<iostream>
  5 #include<algorithm>
  6 #include<string>
  7 #include<iomanip>
  8 #include<memory.h>
  9 #include<time.h>
 10 #include<stdio.h>
 11 #include<stdlib.h>
 12 #include<string.h>
 13 //#include<stdbool.h>
 14 #include<math.h>
 15 #define min(a,b) ((a)<(b)?(a):(b))
 16 #define max(a,b) ((a)>(b)?(a):(b))
 17 #define abs(a) ((a)>0?(a):(-(a)))
 18 #define lowbit(a) (a&(-a))
 19 #define sqr(a) ((a)*(a))
 20 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))
 21 #define mem(a,b) memset(a,b,sizeof(a))
 22 #define eps (1e-8)
 23 #define J 10
 24 #define MAX 0x7f7f7f7f
 25 #define PI 3.14159265358979323
 26 #define N 100004
 27 using namespace std;
 28 typedef long long LL;
 29 int cas,cass;
 30 int n,m,lll,ans;
 31 int fa[N],s[N],last[N];
 32 double c[N];
 33 struct xxx
 34 {
 35     int next,to;
 36 }a[N];
 37 void add(int x,int y)
 38 {
 39     a[++lll].next=last[x];
 40     a[lll].to=y;
 41     last[x]=lll;
 42 }
 43 void cal(int u)
 44 {
 45     int i,v;
 46     for(i=last[u];i;i=a[i].next)
 47     {
 48         v=a[i].to;
 49         cal(v);
 50         s[u]+=s[v];
 51     }
 52     s[u]++;
 53 }
 54 void dfs(int u)
 55 {
 56     int i,v;
 57     for(i=last[u];i;i=a[i].next)
 58     {
 59         v=a[i].to;
 60         c[v]=c[u]+(s[u]-s[v]-1)*0.5+1;
 61         dfs(v);
 62     }
 63 }
 64 void print()
 65 {
 66     int i;
 67     for(i=1;i<=n;i++)
 68     {
 69         printf("%d ",s[i]);
 70     }
 71     puts("");
 72 }
 73 int main()
 74 {
 75     #ifndef ONLINE_JUDGE
 76     freopen("1.txt","r",stdin);
 77 //    freopen("2.txt","w",stdout);
 78     #endif
 79     int i,j;
 80 //    for(scanf("%d",&cas);cas;cas--)
 81 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
 82 //    while(~scanf("%s",s))
 83     while(~scanf("%d",&n))
 84     {
 85         mem(s,0);mem(last,0);lll=0;
 86         for(i=2;i<=n;i++)
 87         {
 88             scanf("%d",&fa[i]);
 89             add(fa[i],i);
 90         }
 91         cal(1);
 92         c[1]=1.0;
 93         dfs(1);
 94         for(i=1;i<=n;i++)
 95             printf("%.1lf ",c[i]);
 96         puts("");
 97     }
 98     return 0;
 99 }
100 /*
101 //
102 
103 //
104 */

View Code