GYM 101086 K.Betrayed（树形DP+概率DP）

GYM 101086 K.Betrayed（树形DP+概率DP）

Description
c棵树，每次从第一棵树开始搜，每次等概率选一个节点作为树根开始dfs，每次dfs花费时间为1秒，如果树的深度超过k则爆栈，需要debug3秒然后从头开始，问在不爆栈的情况下dfs完这c棵树的期望用时
Input
第一行一整数T表示用例组数，每组用例输入两个整数c和k表示树的数量和每次不爆栈的极限深度，之后c行每行首先输入一整数n表示该棵树的点数，然后输入n-1个整数，第i个整数a[i]表示i+1和a[i]之间有一条边
(1<=T<=128,1<=c<=20,1<=k<=1e5,1<=n<=1e5)
Output
输出在不爆栈的情况下dfs完这c棵树的期望用时，保留小数点后四位
Sample Input
3
2 2
2 1
3 1 1
3 5
7 3 4 7 1 5 6
6 1 4 2 1 5
5 1 1 5 1
4 3
4 4 1 1
6 1 2 1 1 5
5 4 1 3 4
1
Sample Output
2.0000
4.6000
6.5000
Solution
首先需要计算出第i棵树不爆栈的概率p[i]，即对于树上每个点j，求出离j点最远的点k到j点的距离，这个是经典树形DP题目，假设有cnt个点树上点到其的最远距离不超过k，那么该棵树不爆栈的概率为p[i]=cnt/n，之后需要求出一棵棵扫树到扫完或者爆栈的期望用时以及不爆栈的概率，以pp[i]表示i~n这些树中爆栈的概率，ee[i]表示对i~n这些树dfs所需的时间，那么有pp[i]=p[i]pp[i+1]+1-p[i]（第一部分表示爆栈在第i棵树后面，那么第i棵树就没有爆栈，第二种表示爆栈在第i棵树），ee[i]=p[i]*ee[i+1]+1+3(1-p[i])（第一部分表示爆栈在第i棵树后面，那么第i棵树没有爆栈，概率为p[i]，用时为ee[i+1]+1，第二部分表示爆栈在第i棵树，概率为1-p[i]，用时为(1-p[i])(3+1)，故总用时为p[i]*ee[i+1]+1+3(1-p[i])），最后1-pp[1]就是没有爆栈的概率，ee[1]/(1-pp[1])就是条件期望
Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 111111
int T,c,k,n,max1[maxn],max2[maxn],dp[maxn];
vector<int>g[maxn];
double p[maxn];
void add(int u,int v)
{g[u].push_back(v);
}
void dfs1(int u,int fa,int deep)
{max1[u]=max2[u]=0;for(int i=0;i<g[u].size();i++){int v=g[u][i];if(v==fa)continue;dfs1(v,u,deep+1);int t=max1[v]+1;if(t>max2[u])max2[u]=t;if(max2[u]>max1[u])swap(max1[u],max2[u]);}
}
void dfs2(int u,int fa)
{for(int i=0;i<g[u].size();i++){int v=g[u][i];if(v==fa)continue;if(max1[v]==max1[u]-1)dp[v]=max(dp[v],max2[u]+1);else dp[v]=max(dp[v],max1[u]+1);dp[v]=max(dp[v],dp[u]+1);dfs2(v,u);}
}
double deal()
{scanf("%d",&n);for(int i=1;i<=n;i++)g[i].clear();for(int i=2;i<=n;i++){int temp;scanf("%d",&temp);add(temp,i),add(i,temp);}dfs1(1,0,0);memset(dp,0,sizeof(dp));dfs2(1,0);int ans=0;for(int i=1;i<=n;i++){dp[i]=max(dp[i],max1[i]);if(dp[i]>k)ans++;}return 1.0*(n-ans)/n;
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&c,&k);for(int i=1;i<=c;i++)p[i]=deal();double pp=0,ee=0;for(int i=c;i>=1;i--){pp=p[i]*pp+1-p[i];ee=p[i]*ee+1+3.*(1-p[i]);}printf("%.4fn",ee/(1.0-pp));}return 0;
}