fork download
copy 
  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;
  23. vector<int> compSize;
  24. void dfsComp(int u,int c){
  25.     comp[u]=c; compSize[c]++;
  26.     for(auto e:g[u]) if(comp[e.to]==-1 && !isBridge[e.id]) dfsComp(e.to,c);
  27. }
  28.  
  29. vector<vector<int>> tree;
  30. vector<int> subSize;
  31. vector<bool> removed;
  32. long long goodPairs=0;
  33.  
  34. vector<long long> freq; // freq[d] = số đỉnh ở khoảng cách d
  35. int maxUsed=0;          // độ sâu lớn nhất đã dùng
  36.  
  37. int getSize(int u,int p){
  38.     subSize[u]=compSize[u];
  39.     for(int v:tree[u]) if(v!=p && !removed[v]) subSize[u]+=getSize(v,u);
  40.     return subSize[u];
  41. }
  42.  
  43. int getCentroid(int u,int p,int n){
  44.     for(int v:tree[u]) if(v!=p && !removed[v]) 
  45.         if(subSize[v]>n/2) return getCentroid(v,u,n);
  46.     return u;
  47. }
  48.  
  49. void collect(int u,int p,int d,vector<pair<int,int>>& nodes){
  50.     nodes.push_back({d,compSize[u]});
  51.     for(int v:tree[u]) if(v!=p && !removed[v]) collect(v,u,d+1,nodes);
  52. }
  53.  
  54. void solveCentroid(int c){
  55.     // reset freq
  56.     for(int i=0;i<=maxUsed;i++) freq[i]=0;
  57.     maxUsed=0;
  58.  
  59.     freq[0] = compSize[c];
  60.     maxUsed = 0;
  61.  
  62.     for(int v:tree[c]) if(!removed[v]){
  63.         vector<pair<int,int>> distSub;
  64.         collect(v,c,1,distSub);
  65.         int localMax=0;
  66.         for(auto [d,_]:distSub) localMax=max(localMax,d);
  67.         maxUsed = max(maxUsed, localMax);
  68.  
  69.         // chuẩn bị suffix để query nhanh
  70.         vector<long long> suff(maxUsed+2,0);
  71.         for(int i=maxUsed;i>=0;i--){
  72.             suff[i] = freq[i] + suff[i+1];
  73.         }
  74.  
  75.         // đếm cặp giữa nhánh này và freq
  76.         for(auto [d,cnt]:distSub){
  77.             int lim = K-d;
  78.             if(lim<0) lim=0;
  79.             if(lim<=maxUsed){
  80.                 long long s = suff[lim];
  81.                 goodPairs += 1LL * cnt * s;
  82.             }
  83.         }
  84.  
  85.         // merge nhánh vào freq
  86.         for(auto [d,cnt]:distSub){
  87.             if(d>maxUsed) maxUsed=d;
  88.             freq[d]+=cnt;
  89.         }
  90.     }
  91. }
  92.  
  93. void decompose(int u){
  94.     int n=getSize(u,-1);
  95.     int c=getCentroid(u,-1,n);
  96.     solveCentroid(c);
  97.     removed[c]=true;
  98.     for(int v:tree[c]) if(!removed[v]) decompose(v);
  99. }
  100.  
  101. int main(){
  102.     ios::sync_with_stdio(false);
  103.     cin.tie(nullptr);
  104.  
  105.     cin>>N>>M>>K;
  106.     g.assign(N+1,{});
  107.     for(int i=1;i<=M;i++){
  108.         int u,v; cin>>u>>v;
  109.         g[u].push_back({v,i});
  110.         g[v].push_back({u,i});
  111.     }
  112.  
  113.     tin.assign(N+1,0); low.assign(N+1,0); isBridge.assign(M+1,0);
  114.     for(int i=1;i<=N;i++) if(!tin[i]) dfsBridge(i,-1);
  115.  
  116.     comp.assign(N+1,-1);
  117.     int compCnt=0;
  118.     for(int i=1;i<=N;i++) if(comp[i]==-1){ compSize.push_back(0); dfsComp(i,compCnt++); }
  119.  
  120.     tree.assign(compCnt,{});
  121.     for(int u=1;u<=N;u++) for(auto e:g[u]) if(isBridge[e.id]){
  122.         int cu=comp[u], cv=comp[e.to];
  123.         if(cu!=cv) tree[cu].push_back(cv);
  124.     }
  125.  
  126.     subSize.assign(compCnt,0);
  127.     removed.assign(compCnt,false);
  128.     freq.assign(N+5,0);
  129.  
  130.     decompose(0);
  131.  
  132.     cout<<goodPairs<<"\n";
  133. }
  134.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
8 9 2
1 5
1 5
2 3
2 6
3 7
4 8
5 6
6 7
7 8
stdout
copy 
8
https://ideone.com/tMbOhV
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!