本文主要是介绍Puzzles（概率dp）（图），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
D. Puzzles
Barney lives in country USC (United States of Charzeh). USC has n cities numbered from 1 through n and n - 1 roads between them. Cities and roads of USC form a rooted tree (Barney's not sure why it is rooted). Root of the tree is the city number 1. Thus if one will start his journey from city 1, he can visit any city he wants by following roads.
Some girl has stolen Barney's heart, and Barney wants to find her. He starts looking for in the root of the tree and (since he is Barney Stinson not a random guy), he uses a random DFS to search in the cities. A pseudo code of this algorithm is as follows:
let starting_time be an array of length n
current_time = 0
dfs(v):current_time = current_time + 1starting_time[v] = current_timeshuffle children[v] randomly (each permutation with equal possibility)// children[v] is vector of children cities of city vfor u in children[v]:dfs(u)
As told before, Barney will start his journey in the root of the tree (equivalent to call dfs(1)).
Now Barney needs to pack a backpack and so he wants to know more about his upcoming journey: for every city i, Barney wants to know the expected value of starting_time[i]. He's a friend of Jon Snow and knows nothing, that's why he asked for your help.
Input
The first line of input contains a single integer n (1 ≤ n ≤ 105) — the number of cities in USC.
The second line contains n - 1 integers p2, p3, ..., pn (1 ≤ pi < i), where pi is the number of the parent city of city number i in the tree, meaning there is a road between cities numbered pi and i in USC.
Output
In the first and only line of output print n numbers, where i-th number is the expected value of starting_time[i].
Your answer for each city will be considered correct if its absolute or relative error does not exceed 10 - 6.
Examples
input
Copy
7 1 2 1 1 4 4
output
Copy
1.0 4.0 5.0 3.5 4.5 5.0 5.0
input
Copy
12 1 1 2 2 4 4 3 3 1 10 8
output
Copy
1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0
题意：给出每个节点的父节点，构成了一张图。从1出发，使用题目代码中的走法（即为dfs），问你从1到每一个点的期望值。
思路：
分析一颗子树：
当前已知节点1的期望为1.0 ->anw[1]=1.0
需要通过节点1递推出节点2、4、5的期望值
1的儿子分别是2、4、5，那么dfs序所有可能的排列是6种：
1：1-2-4-5 （2、4、5节点的儿子没有写出）
2：1-2-5-4
3：1-4-2-5
4：1-4-5-2
5：1-5-2-4
6：1-5-4-2
计算节点2的期望值得时候，当节点2的前面已经排列了num个点，那么节点2的dfs序就要增加num
所以anw[2]的计算分为两部分，第一部分是：anw[2]=anw[1]+1 （节点1通过1步直接到达儿子2、4、5）
第二部分是：当节点1到达节点2的时候贡献是0，种类分别对应(1、2)
当先到达节点4后到节点2的时候贡献(size(4)+size(4)+szie(5))，种类分别对应(3、4)
当先到达节点5后到节点2的时候贡献(size(5)+size(5)+size(4))，种类分别对应(5、6)
而所有的排列对于的概率都是1/6，所以第二部分的贡献就是（0+size(4)*3+size(5)*3）/6 = (size(4)+size(5))/2
仔细推理几颗子树之后：发现anw[v]=anw[u]+1.0+(sz[u]-sz[v]-1)/2.0。
anw[u]+1.0对应第一部分 (sz[u]-sz[v]-1)/2.0 表示的是当前能排在节点v前面的u的儿子的总数 * 0.5
对比1-6的6种排列，任意儿子a、b ，满足a在b前面的概率是0.5
来源：https://blog.csdn.net/libin66/article/details/51918509
每个兄弟节点在自己前面走的概率都是0.5，而一个节点所有的兄弟节点个数为son[a]-son[s[a][i]]-1，乘以0.5即为在自己之前的期望。
#include<bits/stdc++.h>
#define in(a) scanf("%d",&a)
using namespace std;
vector<int> s[100005];
int son[100005];
double ans[100005];void dfs(int a)
{int len=s[a].size();son[a]=len;for(int i=0;i<len;i++){dfs(s[a][i]);son[a]+=son[s[a][i]];}
}void cal(int a)
{int len=s[a].size();for(int i=0;i<len;i++){ans[s[a][i]]=ans[a]+1+0.5*(son[a]-son[s[a][i]]-1);cal(s[a][i]);}
}int main()
{int T,t;in(T);for(int i=1;i<=T;i++)s[i].clear();for(int i=2;i<=T;i++){in(t);s[t].push_back(i);}dfs(1);ans[1]=1.0;cal(1);for(int i=1;i<=T;i++)printf("%.8f ",ans[i]);puts("");return 0;}
这篇关于Puzzles（概率dp）（图）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
