fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. vector<pair<ll,ll>> edge[1000]; // {id, distance}
  6. ll total;
  7.  
  8. namespace sensible{
  9.   // O(N)
  10.   pair<ll,ll> dfs(int x,int up=-1){
  11.     pair<ll,ll> res={0,1};
  12.  
  13.     for (auto y: edge[x]) if (y.first!=up){
  14.       auto rec=dfs(y.first,x);
  15.  
  16.       rec.first+=y.second*rec.second;
  17.  
  18.       total+=rec.first*res.second+res.first*rec.second;
  19.       res.second+=rec.second;
  20.       res.first+=rec.first;
  21.     }
  22.  
  23.     return res;
  24.   }
  25. }
  26.  
  27. namespace stupid{
  28.   ll depth[1000];
  29.   ll sum[1000];
  30.   ll p[1000][20];
  31.  
  32.   // O(N)
  33.   void prep(int x,int up=-1){
  34.     for (int i=1; i<20; i++){
  35.       p[x][i]=p[p[x][i-1]][i-1];
  36.     }
  37.     for (auto y: edge[x]) if (y.first!=up){
  38.       sum[y.first]=sum[x]+y.second;
  39.       depth[y.first]=depth[x]+1;
  40.       p[y.first][0]=x;
  41.       prep(y.first,x);
  42.     }
  43.   }
  44.  
  45.   // O( (logN) * (N^2) )
  46.   void distance(int x,int y){
  47.     total+=sum[x]+sum[y];
  48.  
  49.     if (depth[x]<depth[y]) swap(x,y);
  50.     int lca=x;
  51.     for (int i=20; i--;) if ((depth[x]-depth[y])&(1<<i)) x=p[x][i];
  52.     for (int i=20; i--;) if (p[x][i]!=p[y][i]) x=p[x][i], y=p[y][i];
  53.     if (x!=y) x=p[x][0];
  54.  
  55.     total-=sum[x]*2;
  56.   }
  57. }
  58.  
  59. int main(){
  60.   srand(0x539);
  61.  
  62.   int const n=1000;
  63.   for (int i=1; i<n; i++){
  64.     int j=rand()%i;
  65.     ll w=rand()%33333;
  66.     edge[i].push_back({j,w});
  67.     edge[j].push_back({i,w});
  68.   }
  69.  
  70.   total=0;
  71.   sensible::dfs(0);
  72.   cout<<total<<endl;
  73.  
  74.   total=0;
  75.   stupid::prep(0);
  76.   for (int i=n; i--;) for (int j=i; j--;) stupid::distance(i,j);
  77.   cout<<total<<endl;
  78. }
Success #stdin #stdout 0.08s 3616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
96688699446
96688699446
https://ideone.com/iPH9uw
language:
C++14 (gcc 8.3)
created:
10 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!