Advertisement
Guest User

Untitled

a guest
Apr 29th, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.23 KB | None | 0 0
  1. // POI - Hotels
  2. // incompleto (10/100) , para corrigir
  3. // codeforces.com/profile/trath
  4. // Tiago Souza
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. #define ll long long int
  8. #define eps (ll) 1e9
  9. #define mc (int) 1e4
  10. #define epsi (int) 1e3
  11. #define mp make_pair
  12. #define pb push_back
  13. #define F first
  14. #define S second
  15.  
  16. struct star{
  17. int x, y , z;
  18. };
  19. vector<int> adj[mc];
  20. bool vis[mc];
  21. int dist[mc];
  22. int cont[mc];
  23. void dfs(int x){
  24. vis[x] = true;
  25. for(int i = 0;i<adj[x].size() ; i++){
  26. int v = adj[x][i];
  27. if(!vis[v]){
  28. vis[v] = true;
  29. dist[v] = dist[x] + 1;
  30. cont[dist[v]]++;
  31. }
  32. }
  33. }
  34.  
  35. ll binomial(ll i, ll j){
  36. ll C[i+1][j+1];
  37. ll n , m;
  38. for(ll n = 0 ;n<=i;n++){
  39. for(ll m = 0;m<=min(j,n);m++){
  40. if(m ==0|| n == m){
  41. C[n][m] = 1;
  42. }
  43. else{
  44. C[n][m] = C[n-1][m-1] + C[n-1][m];
  45. C[n][m]%=(ll)1e9 + 7;
  46. }
  47. }
  48. }
  49. return C[i][j];
  50. }
  51.  
  52.  
  53.  
  54. int main(){
  55. int n;
  56. cin>>n;
  57. for(int i = 1;i<n;i++){
  58. int x, y;
  59. cin>>x>>y;
  60. x-- , y--;
  61. adj[x].pb(y);
  62. adj[y].pb(x);
  63. }
  64. dist[0] = 0;
  65. ll resp = 0;
  66. for(int i = 0;i<n;i++){
  67. memset(vis, 0 , n + 1);
  68. memset(dist , 0 , mc);
  69. memset(cont , 0 , mc);
  70. dist[i] = 0;
  71. dfs(i);
  72. for(int j = 1;j<mc;j++){
  73. if(cont[j] >= 3){
  74. resp += binomial(cont[j] , 3);
  75. }
  76. }
  77.  
  78. }
  79. cout<<resp;
  80.  
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement