对于每一棵树,我们要统计以每个点为根的树的最长深度。树形DP统计最长链和次长链+换根就可以。
现在得到统计每棵树的概率p[i]和不能通过的概率q[i]=(1-p[i])。
dp[i]:从第1棵树到第i棵树的期望时间。
dp[i]=dp[i−1]+q[i]∗(1)+pi
我们在第i-1棵树的时候。尝试一次。p[i]成功只用1秒。
有q[i]失败,尝试时间1+重启时间+3+重新从1到i的时间。
化简:dp[i]=(dp[i-1]+1+3*q[i])/(1-q[i]);
代码如下:
#include <bits/stdc++.h> #define LL long long using namespace std; struct Edge{ int to, w, nxt; }E[200005]; int head[200005], cut=0; void AddEdge(int u, int v, int w){ E[++cut]={v, w, head[u]}; head[u]=cut; } int f[200005][2];//以i为根的 最长链 次长链 void dfs(int u, int fa, int ww){ for(int i=head[u]; i; i=E[i].nxt){ int x=E[i].to, w=E[i].w; if(x==fa) continue; dfs(x, u, w); if(f[x][0]+w>=f[u][0]) f[u][1]=f[u][0], f[u][0]=f[x][0]+w; else if(f[x][0]+w>f[u][1]) f[u][1]=f[x][0]+w; } } void dfs2(int u, int fa, int ww){ if(ww>=f[u][0]) f[u][1]=f[u][0], f[u][0]=ww; else if(ww>f[u][1]) f[u][1]=ww; for(int i=head[u]; i; i=E[i].nxt){ int x=E[i].to, w=E[i].w; if(x==fa) continue; if(f[x][0]+w==f[u][0]) dfs2(x, u, f[u][1]+w); else dfs2(x, u, f[u][0]+w); } } int main() { int T; scanf("%d", &T); while(T--){ int c, k; scanf("%d%d", &c, &k); double p[25]={0}, q[25]={0}, dp[25]={0}; for(int cc=1; cc<=c; cc++){ int n; scanf("%d", &n); memset(head, 0, sizeof(head)); cut=0; memset(f, 0, sizeof(f)); for(int i=2; i<=n; i++){ int x; scanf("%d", &x); AddEdge(i, x, 1); AddEdge(x, i, 1); } dfs(1, 0, 0); dfs2(1, 0, 0); int siz=0; for(int i=1; i<=n; i++){ if(f[i][0]<=k) siz++; } p[cc]=1.0*siz/n, q[cc]=(1-p[cc]); } for(int i=1; i<=c; i++){ dp[i]=(dp[i-1]+1+3*q[i])/(1-q[i]); } printf("%.4f\n", dp[c]); } return 0; }