fork download
copy 
  1.  /**********************************************************************************************
  2.     ->                      @author : a_e_kasem
  3.     ->   "Code is an art — let logic be your ink and syntax your rhythm."
  4. ***********************************************************************************************/
  5. //*------------------------------------------------------------------------------------------*//
  6. //                                  ﷽
  7. //                            { وَأَنْ لَيْسَ لِلْإِنْسَانِ إِلَّا مَا سَعَى }
  8. //
  9. //                     فَالجُهدُ يُثمِرُ إنْ تَضافَرَ صَفوُهُ، والعَزمُ يَرفعُ صَرحَ كُلِّ بُنيانِ
  10. //
  11. //                              وَما نَيلُ المَطالِبِ بِالتَمَنّي
  12. //                               وَلَكِن تُؤخَذُ الدُنيا غِلابا
  13. //                                     ***
  14. //                             وَما اِستَعصى عَلى قَومٍ مَنالٌ
  15. //                             إِذا الإِقدامُ كانَ لَهُم رِكابا
  16. //*------------------------------------------------------------------------------------------*//
  17.  
  18. #include <bits/stdc++.h>
  19. using namespace std;
  20.  
  21. #define int long long
  22. #define cinAll(a) for (auto &it : a) cin >> it
  23. #define all(x) (x).begin(), (x).end()
  24. #define NO  void(cout << "NO\n")
  25. #define YES void(cout << "YES\n")
  26.  
  27.  
  28. const int N = 2e5 + 5;
  29. const long double NEG_INF = -1e300L, EPS = 1e-12L;
  30.  
  31. vector<int> G[N];
  32. int sub[N], par[N];
  33. long double logC[N];
  34.  
  35. void reset(int n) {
  36.     for (int i = 1; i <= n; ++i) G[i].clear(), sub[i] = 0, par[i] = 0;
  37. }
  38.  
  39. void dfsSubtree(int root = 1) {
  40.     vector<int> order; order.reserve(N);
  41.     stack<int> st; st.push(root); par[root] = -1;
  42.     while (!st.empty()) {
  43.         int u = st.top(); st.pop();
  44.         order.push_back(u);
  45.         for (auto v : G[u]) if (v != par[u]) par[v] = u, st.push(v);
  46.     }
  47.     for (int i = order.size() - 1; i >= 0; --i) {
  48.         int u = order[i]; sub[u] = 1;
  49.         for (auto v : G[u]) if (v != par[u]) sub[u] += sub[v];
  50.     }
  51. }
  52.  
  53. void preLogC(int n, int k) {
  54.     for (int i = k; i <= n; ++i)
  55.         logC[i] = lgammal(i + 1.0L) - lgammal(k + 1.0L) - lgammal(i - k + 1.0L);
  56. }
  57.  
  58. void solve() {
  59.     int n, k; cin >> n >> k;
  60.     reset(n);
  61.     for (int i = 0; i < n - 1; ++i) {
  62.         int u, v; cin >> u >> v;
  63.         G[u].push_back(v); G[v].push_back(u);
  64.     }
  65.     if (k == 1) return cout << n * n << '\n', void();
  66.  
  67.     preLogC(n, k);
  68.     dfsSubtree();
  69.  
  70.     long long ans = 0;
  71.     for (int v = 1; v <= n; ++v) {
  72.         vector<int> comp;
  73.         for (auto to : G[v])
  74.             comp.push_back(to == par[v] ? n - sub[v] : sub[to]);
  75.  
  76.         vector<long double> B, scaled; long double mx = NEG_INF, tot = 0;
  77.         for (int s : comp) {
  78.             long double val = (s >= k) ? logC[s] : NEG_INF;
  79.             B.push_back(val); mx = max(mx, val);
  80.         }
  81.         for (auto b : B) {
  82.             long double x = (b <= NEG_INF/2) ? 0.0L : expl(b - mx);
  83.             scaled.push_back(x); tot += x;
  84.         }
  85.  
  86.         if (n >= k) {
  87.             long double A = logC[n], f = (tot > 0 ? expl(mx - A) * tot : 0);
  88.             if (f < 1.0L - EPS) ans++;
  89.         }
  90.  
  91.         for (int i = 0; i < (int)comp.size(); ++i) {
  92.             int aj = comp[i], t = n - aj;
  93.             if (!aj || t < k) continue;
  94.             long double A = logC[t], f = (tot - scaled[i] > 0 ? expl(mx - A) * (tot - scaled[i]) : 0);
  95.             if (f < 1.0L - EPS) ans += aj;
  96.         }
  97.     }
  98.     cout << ans << '\n';
  99. }
  100.  
  101.  
  102. void FastIO();
  103.  
  104. int32_t main()
  105. {
  106.     FastIO();
  107.     int t = 1;
  108.     cin >> t;
  109.     while (t--)
  110.     {
  111.         solve();
  112.     }
  113.     return 0;
  114. }
  115.  
  116. void FastIO()
  117. {
  118.     ios::sync_with_stdio(false);
  119.     cin.tie(nullptr);
  120.     cout.tie(nullptr);
  121. }
  122.  
Success #stdin #stdout 0.01s 13404KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/eYy5y6
language:
C++14 (gcc 8.3)
created:
1 day 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!