fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Edge { int to, id; };
  5. int N, M, K;
  6. vector<vector<Edge>> g;
  7. vector<int> tin, low, isBridge;
  8. int timerDFS = 0;
  9.  
  10. void dfsBridge(int u, int pEdge) {
  11.     tin[u] = low[u] = ++timerDFS;
  12.     for (auto e : g[u]) {
  13.         if (e.id == pEdge) continue;
  14.         if (!tin[e.to]) {
  15.             dfsBridge(e.to, e.id);
  16.             low[u] = min(low[u], low[e.to]);
  17.             if (low[e.to] > tin[u]) isBridge[e.id] = 1;
  18.         } else low[u] = min(low[u], tin[e.to]);
  19.     }
  20. }
  21.  
  22. vector<int> comp, compSize;
  23. void dfsComp(int u, int c) {
  24.     comp[u] = c; compSize[c]++;
  25.     for (auto e : g[u]) if (comp[e.to] == -1 && !isBridge[e.id]) dfsComp(e.to, c);
  26. }
  27.  
  28. vector<vector<int>> tree;
  29. vector<int> subSize;
  30. vector<bool> removed;
  31. long long badPairs = 0;
  32.  
  33. int getSize(int u, int p) {
  34.     subSize[u] = compSize[u];
  35.     for (int v : tree[u]) if (v != p && !removed[v]) subSize[u] += getSize(v, u);
  36.     return subSize[u];
  37. }
  38.  
  39. int getCentroid(int u, int p, int n) {
  40.     for (int v : tree[u]) if (v != p && !removed[v]) if (subSize[v] > n/2) return getCentroid(v, u, n);
  41.     return u;
  42. }
  43.  
  44. void collect(int u, int p, int d, vector<pair<int,int>>& nodes) {
  45.     nodes.push_back({d, compSize[u]});
  46.     for (int v : tree[u]) if (v != p && !removed[v]) collect(v, u, d+1, nodes);
  47. }
  48.  
  49. void solveCentroid(int c) {
  50.     int maxDepth = 0;
  51.     for (int v : tree[c]) if (!removed[v]) {
  52.         vector<pair<int,int>> tmp;
  53.         collect(v, c, 1, tmp);
  54.         for (auto [d,_] : tmp) maxDepth = max(maxDepth, d);
  55.     }
  56.     vector<long long> freq(maxDepth+K+5, 0);
  57.     freq[0] = compSize[c];
  58.  
  59.     for (int v : tree[c]) if (!removed[v]) {
  60.         vector<pair<int,int>> distSub;
  61.         collect(v, c, 1, distSub);
  62.  
  63.         for (auto [d, cnt] : distSub) {
  64.             int lim = K - d - 1;
  65.             if (lim >= 0) {
  66.                 lim = min(lim, (int)freq.size()-1);
  67.                 long long s = 0;
  68.                 for (int i=0; i<=lim; i++) s += freq[i];
  69.                 badPairs += 1LL * cnt * s;
  70.             }
  71.         }
  72.  
  73.         for (auto [d,cnt] : distSub) freq[d] += cnt;
  74.     }
  75. }
  76.  
  77. void decompose(int u) {
  78.     int n = getSize(u, -1);
  79.     int c = getCentroid(u, -1, n);
  80.     solveCentroid(c);
  81.     removed[c] = true;
  82.     for (int v : tree[c]) if (!removed[v]) decompose(v);
  83. }
  84.  
  85. int main() {
  86.     ios::sync_with_stdio(false);
  87.     cin.tie(nullptr);
  88.  
  89.     cin >> N >> M >> K;
  90.     g.assign(N+1, {});
  91.     for (int i=1; i<=M; i++) {
  92.         int u,v; cin >> u >> v;
  93.         g[u].push_back({v,i});
  94.         g[v].push_back({u,i});
  95.     }
  96.  
  97.     tin.assign(N+1,0); low.assign(N+1,0); isBridge.assign(M+1,0);
  98.     for (int i=1; i<=N; i++) if (!tin[i]) dfsBridge(i,-1);
  99.  
  100.     comp.assign(N+1,-1);
  101.     int compCnt=0;
  102.     for (int i=1; i<=N; i++) if (comp[i]==-1) { compSize.push_back(0); dfsComp(i,compCnt++); }
  103.  
  104.     tree.assign(compCnt,{});
  105.     for (int u=1; u<=N; u++) for (auto e:g[u]) if (isBridge[e.id]) {
  106.         int cu=comp[u], cv=comp[e.to];
  107.         if (cu!=cv) tree[cu].push_back(cv);
  108.     }
  109.  
  110.     subSize.assign(compCnt,0);
  111.     removed.assign(compCnt,false);
  112.  
  113.     long long total = accumulate(compSize.begin(),compSize.end(),0LL);
  114.     long long totalPairs = total*(total-1)/2;
  115.     decompose(0);
  116.     cout << totalPairs - badPairs << "\n";
  117. }
  118.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin 
8 9 2
1 5
1 5
2 3
2 6
3 7
4 8
5 6
6 7
7 8
stdout 
15
https://ideone.com/anwfmi
language:
C++14 (clang 8.0)
created:
11 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!