Advertisement
Tranvick

tree

Nov 15th, 2014
261
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.80 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 222222;
  8.  
  9. int n, f[N], p[N], d;
  10. long long result;
  11. vector<int> g[N];
  12.  
  13. void input() {
  14.     cin >> n;
  15.     for (int i = 1; i < n; ++i) {
  16.         int x, y;
  17.         cin >> x >> y;
  18.         g[x].push_back(y);
  19.         g[y].push_back(x);
  20.     }
  21. }
  22.  
  23. void calc_fp(int v=1, int parent=-1) {
  24.     p[v] = 1;
  25.     for (size_t i = 0; i < g[v].size(); ++i) {
  26.         int to = g[v][i];
  27.         if (to != parent) {
  28.             calc_fp(to, v);
  29.             if (f[to] + 1 == f[v]) {
  30.                 p[v] += p[to];
  31.             } else if (f[to] + 1 > f[v]) {
  32.                 f[v] = f[to] + 1;
  33.                 p[v] = p[to];
  34.             }
  35.         }
  36.     }
  37. }
  38.  
  39.  
  40. void calc_diam(int v=1, int parent=-1) {
  41.     int max1 = 0, max2 = 0;
  42.     for (size_t i = 0; i < g[v].size(); ++i) {
  43.         int to = g[v][i];
  44.         if (to != parent) {
  45.             calc_diam(to, v);
  46.             max2 = max(max2, f[to] + 1);
  47.             if (max2 > max1) {
  48.                 swap(max1, max2);
  49.             }
  50.         }
  51.     }
  52.     d = max(d, max1 + max2);
  53. }
  54.  
  55.  
  56. void calc_result(int v=1, int parent=-1) {
  57.     int max1 = 0, max2 = 0, p_sum = 0;
  58.     for (size_t i = 0; i < g[v].size(); ++i) {
  59.         int to = g[v][i];
  60.         if (to != parent) {
  61.             calc_result(to, v);
  62.             p_sum += p[to];
  63.             max2 = max(max2, f[to] + 1);
  64.             if (max2 > max1) {
  65.                 swap(max1, max2);
  66.             }
  67.         }
  68.     }
  69.     if (max1 + max2 == d) {
  70.         if (max2 == 0) {
  71.             result += p_sum;
  72.         } else if (max1 != max2) {
  73.             p_sum = 0;
  74.             int p_max = 0;
  75.             for (size_t i = 0; i < g[v].size(); ++i) {
  76.                 int to = g[v][i];
  77.                 if (to != parent) {
  78.                     if (f[to] + 1 == max2) {
  79.                         p_sum += p[to];
  80.                     } else if (f[to] + 1 == max1) {
  81.                         p_max = p[to];
  82.                     }
  83.                 }
  84.             }
  85.             result += p_max * 1ll * p_sum;
  86.         } else if (max1 == max2) {
  87.             p_sum = 0;
  88.             long long temp = 0;
  89.             for (size_t i = 0; i < g[v].size(); ++i) {
  90.                 int to = g[v][i];
  91.                 if (to != parent && f[to] + 1 == max1) {
  92.                     p_sum += p[to];
  93.                 }
  94.             }
  95.             for (size_t i = 0; i < g[v].size(); ++i) {
  96.                 int to = g[v][i];
  97.                 if (to != parent && f[to] + 1 == max1) {
  98.                     temp += p[to] * 1ll * (p_sum - p[to]);
  99.                 }
  100.             }
  101.             result += temp / 2;
  102.         }
  103.     }
  104. }
  105.  
  106.  
  107. int main() {
  108.     input();
  109.     calc_fp();
  110.     calc_diam();
  111.     calc_result();
  112.     cout << result << endl;
  113.     return 0;
  114. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement