Codeforces Round #728 (Div. 2)

c排序再累加最后去个尾求个和

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int mod=1e9+7,inv2=(mod+1)/2;
int ksm(int b,int n){
    int res=1;
    while(n){
        if(n&1) res=1ll*res*b%mod;
        b=1ll*b*b%mod; n>>=1;
    }
    return res;
}
int ans,dis[405],dep[405],f[405][405],c[405][405],fa[405][10];
vector<int> e[405];
vector<int> vec[405];
void dfs(int u,int fath){
    vec[u].clear(); vec[u].push_back(u);
    dep[u]=dep[fath]+1;
    for(auto v:e[u])
    {
        if(v!=fath)
        {
            dfs(v,u);
            for(auto x:vec[v])
            {
                for(auto y:vec[u])
                {
                    int a=x,b=y;
                    if(a<b) swap(a,b);
                    ans=(ans+f[dep[a]-dep[u]][dep[b]-dep[u]])%mod;
                }
            }
            for(auto x:vec[v])
            {
                vec[u].push_back(x);
            }
        }
    }
}
int fac[405],inv[405];
void init(int n){
    fac[0]=1;
    for(int i=1;i<=n;++i)
        fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=ksm(fac[n],mod-2);
    for(int i=n-1;i>=0;--i)
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
int C(int n,int m){
    if(n<0||m<0||n<m) return 0;
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void solve(){
    int n;cin>>n;
    for(int i=1;i<n;++i){
        int u,v;cin>>u>>v;
        e[u].push_back(v),e[v].push_back(u);
    }
    init(n+n);
    for(int y=1;y<=n;++y) f[0][y]=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=0;k<j;++k)
                f[i][j]=(f[i][j]+1ll*ksm(inv2,i+k)*C(i+k-1,k))%mod;
    for(int k=1;k<=n;++k)
        dfs(k,0);
    cout<<1ll*ans*ksm(n,mod-2)%mod;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--) solve();
    return 0;
}