树形\(DP\)

考虑设\(f_{i,j,k}\)表示在\(i\)的子树内，从\(i\)向下的最长链长度为\(j\)，\(i\)子树内直径长度为\(k\)的概率。

然后我们就能发现这个东西直接转移是几乎不可能的。

所以我们在转移时要开个辅助数组\(s_{op,x,y,k}\)，其中\(op\)用于滚存，表示最长链为\(x\)，次长链为\(y\)，子节点子树内直径长度小于等于\(k\)的概率。

然后我们只要枚举子节点，再枚举子节点子树内的链长，就可以采用刷表法简便地\(DP\)转移了。

这样看似\(O(n^5)\)，但如果你采用了记\(Size\)优化转移上界的方法，根据树上背包的复杂度，这里应该是\(O(n^4)\)的 。

最后我们更新\(f_{x,i,max(i+j,k)}\)加上\(s_{op,i,j,k}-s_{op,i,j,k-1}\)。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 60

#define DB double

#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)

#define Gmax(x,y) (x<(y)&&(x=(y)))

using namespace std;

int n,ee,lnk[N+5];struct edge {int to,nxt;}e[N<<1];

class DpSolver

{

	private:

		int g[N+5],l[N+5];DB f[N+5][2*N+5][2*N+5],s[2][2*N+5][2*N+5][2*N+5];

		I void DP(CI x,CI lst)

		{

			RI i,j,k,p,q,op;DB t,v;

			for(g[x]=1,i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&(DP(e[i].to,x),g[x]+=g[e[i].to]);//DP子节点

			for(i=0;i<=2*g[x];++i) s[0][0][0][i]=1;//初始化

			for(op=0,i=lnk[x];i;i=e[i].nxt) if(e[i].to^lst)//枚举子节点

			{

				for(j=0;j<=l[e[i].to];++j) for(k=1;k<=2*g[x];++k) f[e[i].to][j][k]+=f[e[i].to][j][k-1];//处理前缀和，方便转移

				for(op^=1,j=0;j<=l[x];++j) for(k=0;k<=j;++k) for(p=0;p<=2*g[x];++p)//枚举当前状态

				{

					t=s[op^1][j][k][p],s[op^1][j][k][p]=0;//记下当前状态，注意清空原先数组

					for(q=0;q<=l[e[i].to];++q) v=0.5*t*f[e[i].to][q][p],//枚举子树内最长链

						q+1>j?(s[op][q+1][j][p]+=v):(q+1>k?s[op][j][q+1][p]+=v:s[op][j][k][p]+=v),//如果这条边长度为1

						q+2>j?(s[op][q+2][j][p]+=v):(q+2>k?s[op][j][q+2][p]+=v:s[op][j][k][p]+=v);//如果这条边长度为2

				}Gmax(l[x],l[e[i].to]+2);

			}

			for(i=0;i<=l[x];++i) for(j=0;j<=i;++j) for(k=2*g[x];~k;--k)//枚举状态

				f[x][i][max(i+j,k)]+=s[op][i][j][k]-(k?s[op][i][j][k-1]:0),s[op][i][j][k]=0;//将状态更新到f数组中，并清空

		}

	public:

		I void Solve()

		{

			RI i,j;DB ans=0;DP(1,0);//树形DP

			for(i=0;i<=l[1];++i) for(j=i;j<=2*g[1];++j) ans+=f[1][i][j]*j;//统计答案

			printf("%.8lf",ans);//输出答案

		}

}D;

int main()

{

	freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);

	RI i,x,y;for(scanf("%d",&n),i=1;i^n;++i) scanf("%d%d",&x,&y),add(x,y),add(y,x);//读入建边

	return D.Solve(),0;

}