fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. int main(){
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(NULL);
  9.  
  10.     int tt = 1;
  11.     cin >> tt;
  12.  
  13.     while(tt--){
  14.         ll n;
  15.         cin >> n;
  16.  
  17.         vector<vector<ll>> v(n);
  18.         for(ll i = 1; i < n; i++){
  19.             ll x, y;
  20.             cin >> x >> y;
  21.             x--;
  22.             y--;
  23.             v[x].push_back(y);
  24.             v[y].push_back(x);
  25.         }
  26.  
  27.         ll answer = 0;
  28.         vector<ll> ss(n, 1);
  29.         ll md = 1e9 + 7;
  30.  
  31.         auto modpow = [&](ll a, ll b) {
  32.             a %= md;
  33.             ll res = 1;
  34.             while (b > 0) {
  35.                 if (b & 1) res = (res * a) % md;
  36.                 a = (a * a) % md;
  37.                 b >>= 1;
  38.             }
  39.             return res;
  40.         };
  41.  
  42.         auto modDivide = [&](ll G, ll m) {
  43.             return (G % md) * modpow(m, md - 2) % md;
  44.         };
  45.  
  46.         auto solve = [&](const vector<ll>& c) {
  47.             ll s1 = 0, s2 = 0, s3 = 0;
  48.             ll d = c.size();
  49.             for(ll i = 0; i < d; i++){
  50.                 s1 = (s1 + c[i]) % md;
  51.                 s2 = (s2 + c[i] * c[i]) % md;
  52.                 s3 = (s3 + c[i] * c[i] * c[i]) % md;
  53.             }
  54.  
  55.             ll G = (s1 * s1 % md * s1) % md;
  56.             G = (G - (3 * s1 % md * s2) % md + md) % md;
  57.             G = (G + (2 * s3) % md) % md;
  58.             G = modDivide(G, 6);
  59.             return G;
  60.         };
  61.  
  62.         function<void(ll, ll)> dfs = [&](ll u, ll par){
  63.             vector<ll> val;
  64.             for(auto& z : v[u]) {
  65.                 if(z != par){
  66.                     dfs(z, u);
  67.                     val.push_back(ss[z]);
  68.                     ss[u] += ss[z];
  69.                 }
  70.             }
  71.  
  72.             val.push_back(n - ss[u]);
  73.             answer = (answer + solve(val)) % md;
  74.         };
  75.  
  76.         dfs(0, -1);
  77.  
  78.         cout << answer << '\n';
  79.     }
  80.  
  81.     return 0;
  82. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
2
3
1 2
2 3
6
1 2
1 3
2 4
2 5
3 6
stdout
copy 
0
3
https://ideone.com/kFAxew
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!