Advertisement
a53

srh

a53
Mar 3rd, 2017
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.98 KB | None | 0 0
  1. ///autor: Andrei Margeloiu
  2. # include <bits/stdc++.h>
  3. # define MOD 1000000007
  4. # define NR 100005
  5. # define prim 97
  6. using namespace std;
  7.  
  8. ifstream f("srh.in");
  9. ofstream g("srh.out");
  10. vector <int> v[NR];
  11. long long key[NR], sol;
  12. int x, y, n;
  13.  
  14. void DFS (int k, int tata) {
  15. key[k] = 1;
  16. for (auto &x: v[k]) {
  17. if (x != tata) {
  18. DFS (x, k);
  19. key[k] += key[x] * prim;
  20. key[k] %= MOD;
  21. }
  22. }
  23. }
  24.  
  25. int main ()
  26. {
  27. f>>n;
  28. for (int i=1; i<n; ++i) {
  29. f>>x>>y;
  30. v[x].push_back(y);
  31. v[y].push_back(x);
  32. }
  33.  
  34. DFS(1, 0);
  35. sort (key+1, key+n+1);
  36. key[n+1] = -1;
  37. int i = 1, nr = 1;
  38.  
  39. while (i<=n) {
  40. if (key[i] == key[i+1] && i<=n) {
  41. while (key[i] == key[i+1]) {
  42. ++nr;
  43. ++i;
  44. }
  45. sol = sol + 1LL * nr * (nr - 1) / 2;
  46. nr = 1;
  47. } else ++i;
  48. }
  49.  
  50. g<<sol<<"\n";
  51.  
  52. return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement