Advertisement
Guest User

Untitled

a guest
Jan 17th, 2016
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MX_SZ = 5000 + 42;
  6. const int MX_H = 14;
  7. vector<int> g[MX_SZ];
  8. int tin[MX_SZ], tout[MX_SZ], timer = 1, sz[MX_SZ], h[MX_SZ];
  9. int pr[MX_SZ][MX_H];
  10.  
  11. void dfs_pre(int v, int p, int ch)
  12. {
  13. h[v] = ch;
  14. tin[v] = timer;
  15. timer++;
  16. pr[v][0] = p;
  17. for (int i = 1; i < MX_H; i++)
  18. {
  19. pr[v][i] = pr[pr[v][i - 1]][i - 1];
  20. }
  21. for (int u : g[v])
  22. {
  23. if (u != p)
  24. {
  25. dfs_pre(u, v, ch + 1);
  26. sz[v] += sz[u];
  27. }
  28. }
  29. sz[v]++;
  30. tout[v] = timer;
  31. timer++;
  32. return;
  33. }
  34.  
  35. inline bool upper(int v, int u)
  36. {
  37. return tin[v] < tin[u] and tout[v] > tout[u];
  38. }
  39.  
  40. inline int lca(int v, int u)
  41. {
  42. for (int i = MX_H - 1; i >= 0; i--)
  43. {
  44. if (!upper(pr[v][i], u))
  45. {
  46. v= pr[v][i];
  47. }
  48. }
  49. return pr[v][0];
  50. }
  51.  
  52. int main()
  53. {
  54. ios_base::sync_with_stdio(false);
  55. int n;
  56. cin >> n;
  57. for (int i = 0; i < n - 1; i++)
  58. {
  59. int x, y;
  60. cin >> x >> y;
  61. g[x].push_back(y);
  62. g[y].push_back(x);
  63. }
  64. dfs_pre(1, 1, 1);
  65. int ans = 0;
  66. for (int v = 1; v <= n; v++)
  67. {
  68. for (int u = v + 1; u <= n; u++)
  69. {
  70. int cv = v, cu = u, cu1 = -1;
  71. int ch, realh;
  72. bool skip = false;
  73. if (upper(cv, cu) or upper(cu, cv))
  74. {
  75. if (upper(cu, cv))
  76. {
  77. swap(cv, cu);
  78. }
  79. realh = h[cu] - h[cv];
  80. ch = (h[cu] - h[cv] - 1) / 2;
  81. }
  82. else
  83. {
  84. int clca = lca(cv, cu);
  85. if (h[cv] > h[cu])
  86. {
  87. swap(cu, cv);
  88. }
  89. realh = h[cv] + h[cu] - 2 * h[clca];
  90. ch = (realh - 1) / 2;
  91. if (h[cv] == h[cu])
  92. {
  93. skip = true;
  94. int cnt1 = 0;
  95. cu1 = cv;
  96. for (int j = MX_H - 1; j >= 0; j--)
  97. {
  98. if (cnt1 + (1 << j) <= ch)
  99. {
  100. cnt1 += (1 << j);
  101. cu1 = pr[cu1][j];
  102. }
  103. }
  104. }
  105. }
  106. int cnt = 0;
  107. for (int j = MX_H - 1; j >= 0; j--)
  108. {
  109. if (cnt + (1 << j) <= ch)
  110. {
  111. cnt += (1 << j);
  112. cu = pr[cu][j];
  113. }
  114. }
  115. if (sz[cu] == sz[cu1] and skip)
  116. {
  117. ans++;
  118. }
  119. if (skip)
  120. {
  121. continue;
  122. }
  123. if (cu1 == -1)
  124. {
  125. cu1 = pr[cu][0];
  126. }
  127. if (realh % 2 == 0)
  128. {
  129. if (sz[cu] == n - sz[cu1])
  130. {
  131. ans++;
  132. }
  133. }
  134. else
  135. {
  136. if (sz[cu] == n - sz[cu])
  137. {
  138. ans++;
  139. }
  140. }
  141. }
  142. }
  143. cout << ans;
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement