最近从某个地方看到了这个题。。。所以回来补一下题解。

<h1>题目描述</h1>

<h1>题解</h1>

直接求期望不太好求，我们可以考虑求出每一种条件下的概率，最后乘上直径长度就可以了。
我们设 $f_{i,j,k}$ 表示在以 $i$ 为根的子树里，目前不跨过 $i$ 节点的最长链是 $j$，子树的直径是 $k$ 的概率。
转移就用树 dp 合并子树那种方法来做...枚举一下根与待合并的子树之间的边权就可以了。
转移方程就咕了，详情请参考代码。

<h1>代码</h1>

#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair
#define Re register
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(Re int i = a;i <= b;++i)
#define ROF(i,a,b) for(Re int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define ld long double

const double EPS = 1e-9;
const int MAXN = 100+5;

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int cnt,head[MAXN];

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

ld fMAXN[MAXN],gMAXN;int dep[MAXN],chain[MAXN];
inline bool cmp(int a,int b){
    return chain[a] < chain[b];
}

inline void dfs(int v,int fa){
    fv[0] = 1;std::vector<int> ch;
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dfs(e[i].to,v);ch.pb(e[i].to);
    }
    std::sort(all(ch),cmp);
    FOR(k,0,(int)ch.size()-1){
        int t = ch[k];
        FOR(i,0,dep[v]){
            FOR(j,0,chain[v]){
                gi = fv[j];
                fv[j] = 0;
            }
        }
        FOR(i1,0,dep[v]){
            FOR(j1,0,chain[v]){
                if(std::fabs(gi1) <= EPS) continue;
                FOR(i2,0,dep[t]){
                    FOR(j2,0,chain[t]){
                        if(std::fabs(ft[j2]) <= EPS) continue;
                        ld x = gi1  ft[j2]0.5;
                        FOR(kk,1,2){
                            int i = std::max(i1,i2+kk),j = std::max(i1+i2+kk,std::max(j1,j2));
                            fv[j] += x;
                        }
                    }
                }
            }
        }
        chain[v] = std::max(std::max(chain[v],chain[t]),dep[v]+dep[t]+2);
        dep[v] = std::max(dep[v],dep[t]+2);
    }
}

int n,a[MAXN],b[MAXN];

int main(){
    scanf("%d",&n);
    FOR(i,1,n-1){
        int u,v;scanf("%d%d",&u,&v);add(u,v);
    }
    dfs(1,0);
    ld ans = 0;
    FOR(i,0,dep[1]){
        FOR(j,0,chain[1]){
            ans += j*f1[j];
        }
    }
    printf(".10Lfn",ans);
   return 0;
}