1540B - Tree Array - CodeForces Solution

#include<bits/stdc++.h>
#define int long long

const int maxn = 209,modd = 1e9 + 7;
using namespace std;

int n,dep[maxn],fa[maxn][25],f[maxn][maxn];

vector<int> g[maxn];

int qp(int a,int b){
  int res = 1;
  while(b){
    if(b&1)res = (res*a)%modd;
    a = (a*a)%modd;
    b>>=1;
  }
  return res % modd;
}

void dfs(int u,int f){
  dep[u] = dep[f] + 1;
  fa[u][0] = f;
  for(int i = 1;i<=20;++i)
    fa[u][i] = fa[fa[u][i-1]][i-1];

  for(int v : g[u]){
    if(v!=f){
      dfs(v,u);
    }
  }
}

int lca(int x,int y){
  if(dep[x]>dep[y])swap(x,y);
  for(int i = 20;i>=0;i--)if(dep[fa[y][i]]>=dep[x])y = fa[y][i];
  if(x==y)return x;
  for(int i = 20;i>=0;i--)if(fa[x][i]!=fa[y][i])x = fa[x][i],y = fa[y][i];
  return fa[x][0];
}

signed main(){
  scanf("%lld",&n);
  for(int i = 1,u,v;i<n;++i){
    scanf("%lld%lld",&u,&v);
    g[u].push_back(v),g[v].push_back(u);
  }

  int inv2 = qp(2,modd-2);
  for(int i = 1;i<=n;++i)f[0][i] = 1;
  for(int i = 1;i<=n;++i){
    for(int j = 1;j<=n;++j){
      f[i][j] = (f[i-1][j] + f[i][j-1])*inv2%modd;
    }
  }

  int ans = 0;
  for(int i = 1;i<=n;++i){
    dfs(i,0);
    for(int j = 1;j<=n;++j){
      for(int k = 1;k<j;++k){
	int _lca = lca(j,k);
	ans = (ans + f[dep[j] - dep[_lca]][dep[k] - dep[_lca]])%modd;
      }
    }
  }

  printf("%lld",ans*qp(n,modd-2)%modd);
}