【题解】Hihocoder 1146 Dark Fores

请注意,本文编写于 98 天前,最后修改于 98 天前,其中某些信息可能已经过时。

Problem

给定一棵树,每条边边权可能是 $1$ 或 $0$ ,求直径的期望长度

Thought

考试没想出来的一道简单题

设 $f[i][j][k]$ 为当前根节点为 $i$ ,子树中直径为 $j$ ,当前最长链为 $k$ 的概率

暴力转移就好了...

我是个智障,不要和我说话,否则你会变傻

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 110;
#define double long double
struct Edge {
    int t, n;
}e[N << 1];
int head[N], Etot;
double f[N][N][N];
double nf[N][N];
int n, siz[N];

void addedge(int u, int v) {
    e[++ Etot] = {v, head[u]};
    head[u] = Etot;
}
void dfs(int x, int _f) {
    siz[x] = 1;
    f[x][0][0] = 1;// 现在根为 1 ,直径为 0 , 最长链为 0
    for(int i = head[x]; i; i = e[i].n) {
        if(e[i].t == _f) continue;
        dfs(e[i].t, x);
        int y = e[i].t;
        for(int dx = 0; dx < siz[x]; ++ dx)
            for(int lx = 0; lx < siz[x]; ++ lx)
                for(int dy = 0; dy < siz[y]; ++ dy)
                    for(int ly = 0; ly < siz[y]; ++ ly) {
                        nf[max(max(dx, dy), (lx + ly))][max(lx, ly)] += 0.5 * f[x][dx][lx] * f[y][dy][ly];
                        nf[max(max(dx, dy), (lx + ly + 1))][max(lx, ly + 1)] += 0.5 * f[x][dx][lx] * f[y][dy][ly];
                    }
        siz[x] += siz[y];
        for(int dx = 0; dx < siz[x]; ++ dx)
            for(int lx = 0; lx < siz[x]; ++ lx) {
                f[x][dx][lx] = nf[dx][lx];
                nf[dx][lx] = 0;
            }
    }

}
int main() {
    n = read();
    for(int i = 1; i < n; ++ i) {
        int u = read(), v = read();
        addedge(u, v);
        addedge(v, u);
    }
    dfs(1, 0);
    double ans = 0;
    for(int i = 0; i < siz[1]; ++ i)
        for(int j = 0; j < siz[1]; ++ j)
            ans += f[1][i][j] * i;
    printf("%.10Lf\n", ans);
    return 0;
}
Comments

添加新评论