fork(3) download
  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
stdin
Standard input is empty
stdout
96688699446
96688699446