fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using PII = pair<ll, ll>;
  5. #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
  6. #define REP(i, n) FOR(i, 0, n)
  7. #define ALL(x) x.begin(), x.end()
  8. template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
  9. template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
  10. struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
  11. #ifdef DEBUG_ 
  12. #include "../program_contest_library/memo/dump.hpp"
  13. #else
  14. #define dump(...)
  15. #endif
  16. const ll INF = 1LL<<60;
  17.  
  18. template<ll MOD>
  19. struct modint {
  20.     ll x;
  21.     modint(): x(0) {}
  22.     modint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}
  23.     static constexpr ll mod() { return MOD; }
  24.     // e乗
  25.     modint pow(ll e) {
  26.         ll a = 1, p = x;
  27.         while(e > 0) {
  28.             if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
  29.             else {a = (a*p) % MOD; e--;}
  30.         }
  31.         return modint(a);
  32.     }
  33.     modint inv() const {
  34.         ll a=x, b=MOD, u=1, y=1, v=0, z=0;
  35.         while(a) {
  36.             ll q = b/a;
  37.             swap(z -= q*u, u);
  38.             swap(y -= q*v, v);
  39.             swap(b -= q*a, a);
  40.         }
  41.         return z;
  42.     }
  43.     // Comparators
  44.     bool operator <(modint b) { return x < b.x; }
  45.     bool operator >(modint b) { return x > b.x; }
  46.     bool operator<=(modint b) { return x <= b.x; }
  47.     bool operator>=(modint b) { return x >= b.x; }
  48.     bool operator!=(modint b) { return x != b.x; }
  49.     bool operator==(modint b) { return x == b.x; }
  50.     // Basic Operations
  51.     modint operator+(modint r) const { return modint(*this) += r; }
  52.     modint operator-(modint r) const { return modint(*this) -= r; }
  53.     modint operator*(modint r) const { return modint(*this) *= r; }
  54.     modint operator/(modint r) const { return modint(*this) /= r; }
  55.     modint &operator+=(modint r) {
  56.         if((x += r.x) >= MOD) x -= MOD;
  57.         return *this;
  58.     }
  59.     modint &operator-=(modint r) {
  60.         if((x -= r.x) < 0) x += MOD;
  61.         return *this;
  62.     }
  63.     modint &operator*=(modint r) {
  64.     #if !defined(_WIN32) || defined(_WIN64)
  65.         x = x * r.x % MOD; return *this;
  66.     #endif
  67.         unsigned long long y = x * r.x;
  68.         unsigned xh = (unsigned) (y >> 32), xl = (unsigned) y, d, m;
  69.         asm(
  70.             "divl %4; \n\t"
  71.             : "=a" (d), "=d" (m)
  72.             : "d" (xh), "a" (xl), "r" (MOD)
  73.         );
  74.         x = m;
  75.         return *this;
  76.     }
  77.     modint &operator/=(modint r) { return *this *= r.inv(); }
  78.     // increment, decrement
  79.     modint operator++() { x++; return *this; }
  80.     modint operator++(signed) { modint t = *this; x++; return t; }
  81.     modint operator--() { x--; return *this; }
  82.     modint operator--(signed) { modint t = *this; x--; return t; }
  83.     // 平方剰余のうち一つを返す なければ-1
  84.     friend modint sqrt(modint a) {
  85.         if(a == 0) return 0;
  86.         ll q = MOD-1, s = 0;
  87.         while((q&1)==0) q>>=1, s++;
  88.         modint z=2;
  89.         while(1) {
  90.             if(z.pow((MOD-1)/2) == MOD-1) break;
  91.             z++;
  92.         }
  93.         modint c = z.pow(q), r = a.pow((q+1)/2), t = a.pow(q);
  94.         ll m = s;
  95.         while(t.x>1) {
  96.             modint tp=t;
  97.             ll k=-1;
  98.             FOR(i, 1, m) {
  99.                 tp *= tp;
  100.                 if(tp == 1) { k=i; break; }
  101.             }
  102.             if(k==-1) return -1;
  103.             modint cp=c;
  104.             REP(i, m-k-1) cp *= cp;
  105.             c = cp*cp, t = c*t, r = cp*r, m = k;
  106.         }
  107.         return r.x;
  108.     }
  109.  
  110.     template<class T>
  111.     friend modint operator*(T l, modint r) { return modint(l) *= r; }
  112.     template<class T>
  113.     friend modint operator+(T l, modint r) { return modint(l) += r; }
  114.     template<class T>
  115.     friend modint operator-(T l, modint r) { return modint(l) -= r; }
  116.     template<class T>
  117.     friend modint operator/(T l, modint r) { return modint(l) /= r; }
  118.     template<class T>
  119.     friend bool operator==(T l, modint r) { return modint(l) == r; }
  120.     template<class T>
  121.     friend bool operator!=(T l, modint r) { return modint(l) != r; }
  122.     // Input/Output
  123.     friend ostream &operator<<(ostream& os, modint a) { return os << a.x; }
  124.     friend istream &operator>>(istream& is, modint &a) { 
  125.         is >> a.x;
  126.         a.x = ((a.x%MOD)+MOD)%MOD;
  127.         return is;
  128.     }
  129.     friend string to_frac(modint v) {
  130.         static map<ll, PII> mp;
  131.         if(mp.empty()) {
  132.             mp[0] = mp[MOD] = {0, 1};
  133.             FOR(i, 2, 1001) FOR(j, 1, i) if(__gcd(i, j) == 1) {
  134.                 mp[(modint(i) / j).x] = {i, j};
  135.             }
  136.         }
  137.         auto itr = mp.lower_bound(v.x);
  138.         if(itr != mp.begin() && v.x - prev(itr)->first < itr->first - v.x) --itr;
  139.         string ret = to_string(itr->second.first + itr->second.second * ((int)v.x - itr->first));
  140.         if(itr->second.second > 1) {
  141.             ret += '/';
  142.             ret += to_string(itr->second.second);
  143.         }
  144.         return ret;
  145.     }
  146. };
  147. using mint = modint<1000000007>;
  148.  
  149. int main(void) {
  150.     ll n, m;
  151.     cin >> n >> m;
  152.     vector<vector<ll>> g(n);
  153.     REP(i, n-1) {
  154.         ll a, b;
  155.         cin >> a >> b;
  156.         a--, b--;
  157.         g[a].push_back(b);
  158.         g[b].push_back(a);
  159.     }
  160.  
  161.     vector<ll> sz(n), dead(n);
  162.     auto find_centroid = [&](ll root) {
  163.         auto get_size = [&](auto &&self, ll v, ll p) -> void {
  164.             sz[v] = 1;
  165.             for(auto to: g[v]) if(to != p && !dead[to]) {
  166.                 self(self, to, v);
  167.                 sz[v] += sz[to];
  168.             }
  169.         };
  170.         get_size(get_size, root, -1);
  171.         auto dfs = [&](auto &&self, ll v, ll p) -> ll {
  172.             for(auto to: g[v]) if(to != p && !dead[to]) {
  173.                 if(sz[to] > sz[root]/2) return self(self, to, v);
  174.             }
  175.             return v;
  176.         };
  177.         return dfs(dfs, root, -1);
  178.     };
  179.  
  180.     mint ret = 0;
  181.     vector<ll> cnt_dist(n);
  182.     auto centroid_decomposition = [&](auto &&self, ll root) -> void {
  183.         ll c = find_centroid(root);
  184.         dead[c] = true;
  185.         for(auto to: g[c]) if(!dead[to]) {
  186.             self(self, to);
  187.         }
  188.  
  189.         vector<vector<ll>> dist;
  190.         auto dfs = [&](auto &&self, ll v, ll p, ll d) -> void {
  191.             dist.back().emplace_back(d);
  192.             for(auto to: g[v]) if(to!=p && !dead[to]) {
  193.                 self(self, to, v, d+1);
  194.             }
  195.         };
  196.         dist.push_back({0});
  197.         for(auto to: g[c]) if(!dead[to]) {
  198.             dist.emplace_back();
  199.             dfs(dfs, to, -1, 1);
  200.             sort(ALL(dist.back()));
  201.         }
  202.  
  203.         vector<ll> flat;
  204.         for(auto v: dist) for(auto i: v) flat.push_back(i);
  205.         sort(ALL(flat));
  206.  
  207.         for(auto v: dist) for(auto i: v) {
  208.             // 距離 m-i の頂点が何個？
  209.             auto lb1 = lower_bound(ALL(flat), m-i);
  210.             auto ub1 = upper_bound(ALL(flat), m-i);
  211.             ret += ub1 - lb1;
  212.             auto lb2 = lower_bound(ALL(v), m-i);
  213.             auto ub2 = upper_bound(ALL(v), m-i);
  214.             ret -= ub2 - lb2;
  215.         }
  216.  
  217.         dead[c] = false;
  218.     };
  219.     centroid_decomposition(centroid_decomposition, 0);
  220.  
  221.     ret *= m;
  222.     ret *= m+1;
  223.     ret /= 2;
  224.     cout << ret/2 << endl;
  225.  
  226.     return 0;
  227. }
Runtime error #stdin #stdout 0s 4560KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/YZcEiI
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!