【每日一题】树形dp专题 Betrayed C++ 题解

对于每一棵树，我们要统计以每个点为根的树的最长深度。树形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;
}