Advertisement
Guest User

Untitled

a guest
Jan 17th, 2016
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.71 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<vector>
  4. #include<cmath>
  5. #include<algorithm>
  6. #include<memory.h>
  7. #include<map>
  8. #include<set>
  9. #include<queue>
  10. #include<list>
  11. #include<sstream>
  12. #include<cstring>
  13. #include<numeric>
  14. using namespace std;
  15.  
  16. const int N = 6e3;
  17.  
  18. vector<int> g[N];
  19. int n;
  20.  
  21.  
  22. int ans[N];
  23. int root;
  24. int parent[N];
  25. bool used[N];
  26. int order[N];
  27. int lvl[N];
  28. int first[N];
  29. int id = 0;
  30. int pcnt[N];
  31.  
  32. void addEdge(int a, int b) {
  33.     g[a].push_back(b);
  34.     g[b].push_back(a);
  35. }
  36.  
  37. bool pu[N];
  38.  
  39. void p_dfs(int v) {
  40.     pu[v] = true;
  41.     for (auto c : g[v]) {
  42.         if (!pu[c]) {
  43.             p_dfs(c);
  44.             pcnt[v] += pcnt[c] + 1;
  45.         }
  46.     }
  47. }
  48.  
  49. void dfs(int v, int path, int s) {
  50.     if (first[v] == -1) {
  51.         first[v] = id;
  52.     }
  53.     order[id++] = v;
  54.     lvl[v] = s;
  55.     ans[v] = path;
  56.     used[v] = true;
  57.     for (auto & i : g[v]) {
  58.         if (!used[i]) {
  59.             parent[i] = v;
  60.             dfs(i, path + 1, s + 1);
  61.             order[id++] = v;
  62.         }
  63.     }
  64.  
  65. }
  66.  
  67.  
  68.  
  69. struct t {
  70.     int val, num;
  71.     t() : val(), num() {}
  72.     t(int v, int n) : val(v), num(n) {}
  73. };
  74.  
  75. struct interval_tree {
  76. private:
  77.     t tree[4 * N];
  78. public:
  79.     void build(int v, int tl, int tr) {
  80.         if (tl == tr) {
  81.             tree[v] = t(lvl[order[tl]], order[tl]);
  82.         }
  83.         else {
  84.             int tm = (tl + tr) / 2;
  85.             build(v * 2, tl, tm);
  86.             build(v * 2 + 1, tm + 1, tr);
  87.             if (tree[v * 2].val > tree[v * 2 + 1].val) {
  88.                 tree[v] = tree[v * 2 + 1];
  89.             }
  90.             else {
  91.                 tree[v] = tree[v * 2];
  92.             }
  93.         }
  94.     }
  95.     t qmin(int v, int tl, int tr, int l, int r) {
  96.         if (l > r)
  97.             return t(INT32_MAX, -1);
  98.         if (l == tl && r == tr)
  99.             return tree[v];
  100.         int tm = (tl + tr) / 2;
  101.         t left = qmin(v * 2, tl, tm, l, min(r, tm));
  102.         t right = qmin(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r);
  103.         if (left.val > right.val) {
  104.             return right;
  105.         }
  106.         return left;
  107.     }
  108. };
  109. interval_tree tree;
  110.  
  111.  
  112.  
  113.  
  114. int main() {
  115.     //freopen("input.txt", "r", stdin);
  116.    
  117.     scanf("%d", &n);
  118.     for (int i = 0; i < n - 1; i++) {
  119.         int a, b;
  120.         scanf("%d%d", &a, &b);
  121.         addEdge(a - 1, b - 1);
  122.     }
  123.     root = 0;
  124.     fill_n(first, N, -1);
  125.     first[root] = 0;
  126.     dfs(root, 0, 0);
  127.     tree.build(1, 0, id - 1);
  128.     p_dfs(root);
  129.  
  130.     int res = 0;
  131.  
  132.     for (int i = 0; i < n; i++) {
  133.         for (int j = i + 1; j < n; j++) {
  134.             t lca = tree.qmin(1, 0, id - 1, min(first[i], first[j]), max(first[i], first[j]));
  135.  
  136.             int nlca = lca.num;
  137.            
  138.             if (nlca == i) {
  139.                 int da = n - 1 - pcnt[j] - 1 - (ans[j] - ans[i] - 1);
  140.                 int db = pcnt[j];
  141.                 if (da == db) {
  142.                     res++;
  143.                     //printf("%d %d: %d %d %d\n", i, j, da, db, 1);
  144.                 }
  145.             }
  146.             else if (nlca == j) {
  147.                 int da = n - 1 - pcnt[i] - 1 - (ans[i] - ans[j] - 1);
  148.                 int db = pcnt[i];
  149.                 if (db == da) {
  150.                     res++;
  151.                     //printf("%d %d: %d %d %d\n", i, j, da, db, 2);
  152.                 }
  153.             }
  154.             else {
  155.                 int da;
  156.                 int db;
  157.                 if (ans[i] != ans[j]) {
  158.                     if (ans[i] > ans[j]) {
  159.                         int cur1 = i;
  160.                         while (parent[cur1] != nlca) {
  161.                             if (ans[i] - ans[parent[cur1]] < ans[j] + ans[parent[cur1]] - 2 * ans[nlca])
  162.                                 cur1 = parent[cur1];
  163.                             else
  164.                                 break;
  165.                         }
  166.  
  167.                         da = pcnt[cur1];
  168.                         db = n - da - 2;
  169.                     }
  170.                     else {
  171.                         int cur1 = j;
  172.                         while (parent[cur1] != nlca) {
  173.                             if (ans[j] - ans[parent[cur1]] < ans[i] + ans[parent[cur1]] - 2 * ans[nlca])
  174.                                 cur1 = parent[cur1];
  175.                             else
  176.                                 break;
  177.                         }
  178.  
  179.                         db = pcnt[cur1];
  180.                         da = n - db - 2;
  181.                     }
  182.                 }
  183.                 else {
  184.                     int cur1 = i;
  185.                     while (parent[cur1] != nlca) {
  186.                         cur1 = parent[cur1];
  187.                     }
  188.                     da = pcnt[cur1];
  189.                     cur1 = j;
  190.                     while (parent[cur1] != nlca) {
  191.                         cur1 = parent[cur1];
  192.                     }
  193.                     db = pcnt[cur1];
  194.                 }
  195.                 if (da == db) {
  196.                     res++;
  197.                     //printf("%d %d: %d %d %d\n", i, j, da, db, 2);
  198.                 }
  199.             }
  200.         }
  201.     }
  202.  
  203.     printf("%d", res);
  204.  
  205.     return 0;
  206. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement