题目地址：

 

题目给出的数据为一棵树，dfs扫描每条边，假设去掉某条边，则左边 x 个点，右边 n-x 个点，则经过该条边共有 x*(n-x) 种组合，又因为 1~n 全排列有 n! 种，故 a~b，包含 b~a 这条边的贡献为 (n-x)*x*2*(n-1)!*w;

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 #define LL long long 7 const int MOD = 1e9+7; 8 const int N = 1e5+5; 9 struct EDGE {10     LL to, length;11 };12 vector
        
          edge[N];13 LL n, factorial[N], lchild[N], w[N];14 15 int dfs(int k, int pre) {16     int size = edge[k].size(), ans=1;17     for(int i=0; i