首页 > 代码库 > Codeforces Round #362 (Div. 1) B. Puzzles 树形dp，概率

Codeforces Round #362 (Div. 1) B. Puzzles 树形dp，概率

2024-09-25 03:34:39   213人阅读

题目链接：

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

题意：

一个树，dfs遍历子树的顺序是随机的。所对应的子树的dfs序也会不同。输出每个节点的dfs序的期望

思路：

http://www.cnblogs.com/01world/p/5795498.html

假设四个子节点为A，B，C，D，因为排列等可能，所以A在B前面的概率跟A在B后面的概率相等，C和D对于A而言一样。所以遍历A的时间期望就是( t(B) + t(C) + t(D) )/2 + P。其中t(B)是访问B节点及其子树所需时间，尽管是随机排列，但是B子树中的节点树是确定的，所以t(B)可以确定，P是A的父节点访问时间的期望。

转移就是  dp[v]=dp[u]+1.0 + (sz[u]-sz[v]-1)/2.0  前面一部分是从父节点u直接走到v的期望，后面是前面走过了u的其它子节点到达v的期望

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
12     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 int n,sz[maxn];
19 vector<int> g[maxn];
20 double ans[maxn];
21 
22 void dfs1(int x){
23     sz[x] = 1;
24     for(int i=0; i<(int)g[x].size(); i++){
25         int v = g[x][i];
26         dfs1(v);
27         sz[x] += sz[v];
28     }
29 }
30 
31 void dfs2(int u){
32     for(int i=0; i<(int)g[u].size(); i++){
33         int v = g[u][i];
34         ans[v] = ans[u]+1 + (sz[u]-sz[v]-1)*1.0/2;
35         dfs2(v);
36     }
37 }
38 
39 int main(){
40     cin >> n;
41     for(int i=2; i<=n; i++){
42         int x = read();
43         g[x].push_back(i);
44     }
45 
46     dfs1(1);
47     ans[1] = 1.0;
48     dfs2(1);
49 
50     for(int i=1; i<=n; i++)
51         printf("%.1f ",ans[i]);
52     puts("");
53 
54 
55     return 0;
56 }

 

Codeforces Round #362 (Div. 1) B. Puzzles 树形dp，概率


联系
我们