fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define maxn 5005
  6.  
  7. int n,i,j,x,y,z,rr;
  8. vector<int> bl,v[maxn],g[maxn];
  9. long long ans;
  10.  
  11. void dfs(int x,int pred,int dep,int fr,int sub){
  12.     v[dep].push_back(sub);
  13.     for(int i=0;i<(int)g[x].size();i++){
  14.         if(g[x][i]==fr||g[x][i]==pred)continue;
  15.         dfs(g[x][i],x,dep+1,fr,sub);
  16.     }
  17. }
  18.  
  19. long long calc(vector<int> a){
  20.     int n=(int)a.size();
  21.     long long tot=0,pairs=0,sum=0;
  22.     for(int i=0;i<n;i++){
  23.         tot+=pairs*a[i];
  24.         pairs+=sum*a[i];
  25.         sum+=a[i];
  26.     }
  27.     return tot;
  28. }
  29.  
  30. int main(){
  31.     //freopen("input.txt","r",stdin);
  32.     //freopen("output.txt","w",stdout);
  33.     scanf("%d",&n);
  34.     for(int i=1;i<n;i++){
  35.         scanf("%d%d",&x,&y);
  36.         g[x].push_back(y);
  37.         g[y].push_back(x);
  38.     }
  39.     for(int i=1;i<=n;i++){
  40.         for(int j=1;j<=n;j++)v[j].clear();
  41.         for(int j=0;j<(int)g[i].size();j++)dfs(g[i][j],-1,1,i,j);
  42.         for(int j=1;j<=n;j++)if(!v[j].empty()){
  43.             sort(v[j].begin(),v[j].end());
  44.             z=0;
  45.             bl.clear();
  46.             while(z<v[j].size()){
  47.                 rr=z;
  48.                 for(int q=z+1;q<(int)v[j].size();q++)
  49.                     if(v[j][q]==v[j][z])rr++;else break;
  50.                 bl.push_back(rr-z+1);
  51.                 z=rr+1;
  52.             }
  53.             ans+=calc(bl);
  54.         }
  55.     }
  56.     printf("%lld\n",ans);
  57.  
  58.     return 0;
  59. }
Success #stdin #stdout 0s 3584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/WA752g
language:
C++14 (gcc 8.3)
created:
8 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!