题意：
思路
考虑m很小，分类讨论就行。
如果环是m的话，那么中间两条边，也就是说在A , B树的环的长度为m − 2
以m = = 5为例，在A , B树的环长度为3，可以是A 2 + B 1和A 1 + B 2。
也就是说从A树里选择长度为2的路径，从B树里选择长度为1的路径。
所以记g a i表示A树里长度为i的路径种数，g b i表示B树里长度为i的路径长度。这两个数组可以通过b fs求出来。
从A的路径端点向B的路径端点连边，方案数为2
对于A树，两个点已经确定了，其余点任意连边的方案数为( n − 2 ) !
总的概率为1 n !约分后就变成了2 ∗ ( g a 1 ∗ g b 2 + g a 2 ∗ g b 1 ) / ( n ∗ ( n − 1 ) )
其他也同理。
代码
#pragma GCC optimize(3) #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll #define x first #define y second inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } #define read read() char F[200]; inline void out(I_int x) { if (x == 0) return (void) (putchar('0')); I_int tmp = x > 0 ? x : -x; if (x < 0) putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0) putchar(F[--cnt]); //cout<<" "; } ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int inf=0x3f3f3f3f; const ll mod=998244353; const ll INF = 0x3f3f3f3f3f3f3f3f; const int maxn=500,maxm=3e6+7; const double PI = atan(1.0)*4; #define rep(i, a, b) for (int i = (a); i <= (b); ++i) vector<int>ea[310],eb[310]; ll ga[10],gb[10]; ll dep[310]; void bfs1(int s){ memset(dep,0x3f,sizeof dep); queue<int>q;q.push(s);dep[s]=0; while(!q.empty()){ int t=q.front();q.pop(); for(int i=0;i<ea[t].size();i++){ int j=ea[t][i]; if(dep[j]>dep[t]+1){ dep[j]=dep[t]+1; q.push(j); } } } } void bfs2(int s){ memset(dep,0x3f,sizeof dep); queue<int>q;q.push(s);dep[s]=0; while(!q.empty()){ int t=q.front();q.pop(); for(int i=0;i<eb[t].size();i++){ int j=eb[t][i]; if(dep[j]>dep[t]+1){ dep[j]=dep[t]+1; q.push(j); } } } } int main(){ ll n=read,m=read; rep(i,1,n-1){ int u=read,v=read; ea[u].push_back(v); ea[v].push_back(u); } rep(i,1,n-1){ int u=read,v=read; eb[u].push_back(v); eb[v].push_back(u); } rep(i,1,n){ bfs1(i); rep(j,1,n){ if(dep[j]>0&&dep[j]<=m) ga[dep[j]]++; } } rep(i,1,n){ bfs2(i); rep(j,1,n){ if(dep[j]>0&&dep[j]<=m) gb[dep[j]]++; } } rep(i,0,9){ ga[i]/=2;gb[i]/=2; // cout<<i<<" "<<ga[i]<<" "<<gb[i]<<"\n"; } double ans; if(m==3) ans=0.0000; else if(m==4){ if(n-1<=0){ ans=0.0000; } else ans=2.0*(n-1)*(n-1)/(n*(n-1)); } else if(m==5){ if(n-1<=0){ ans=0.0000; } else ans=2.0*(ga[2]*gb[1]+ga[1]*gb[2])/(n*(n-1)); } else if(m==6){ if(n-1<=0){ ans=0.0000; } else ans=2.0*(ga[2]*gb[2]+ga[1]*gb[3]+ga[3]*gb[1])/(n*(n-1)); } else if(m==7){ if(n-1<=0){ ans=0.0000; } else ans=2.0*(ga[1]*gb[4]+ga[2]*gb[3]+ga[3]*gb[2]+ga[4]*gb[1])/(n*(n-1)); } printf("%.4lf\n",ans); return 0; } /* 5 6 1 2 2 3 3 4 4 5 1 2 2 3 3 4 #2.5 4 5 1 2 2 3 3 4 1 2 2 3 3 4 #2.0000 */
