Advertisement
Guest User

519E

a guest
May 24th, 2016
197
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.49 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. typedef long long ll;
  6. using namespace std;
  7. using namespace __gnu_pbds;
  8.  
  9. template <typename T>
  10. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
  11.  
  12. #define all(x) x.begin(), x.end()
  13. #define f(i,a,b) for(int i = (a); i <= (b); i++)
  14. #define fd(i,a,b) for(int i = (a); i >= (b); i--)
  15. #define mp make_pair
  16. #define faster_io() ios_base::sync_with_stdio(false)
  17. #define pb push_back
  18. #define pii pair<int,int>
  19. #define SZ(x) ((int)x.size())
  20. #define vii vector<pair<int,int>>
  21.  
  22. const int INF = 1000000005;
  23. const ll INFLL = 100000000000000002ll;
  24. const ll MOD = 10000000;
  25.  
  26. // ----------------------------------------------------------------------------------------------------------
  27.  
  28. int D[100005], L[100005][18], N, Q, Size[100005];
  29. vector<int> E[100005];
  30.  
  31. int get(int n, int dist)
  32. {
  33.     f(i,0,17) if(dist&(1<<i)) n = L[n][i];
  34.     return n;
  35. }
  36.  
  37. int lca(int a, int b)
  38. {
  39.     if(D[a] < D[b]) return lca(b,a);
  40.     int diff = D[a] - D[b];
  41.     f(i,0,17) if(diff&(1<<i)) a = L[a][i];
  42.     if(a == b) return a;
  43.     fd(i,17,0) if(L[a][i] != L[b][i]) a = L[a][i], b = L[b][i];
  44.     return L[a][0];
  45. }
  46.  
  47. void dfs(int n, int p, int d)
  48. {
  49.     D[n] = d;
  50.     L[n][0] = p;
  51.     Size[n] = 1;
  52.     for(int v : E[n]) if(v != p)
  53.     {
  54.         dfs(v,n,d+1);
  55.         Size[n] += Size[v];
  56.     }
  57. }
  58.  
  59. int main()
  60. {
  61.     cin >> N;
  62.     f(i,1,N-1)
  63.     {
  64.         int a,b;
  65.         scanf("%d %d", &a, &b);
  66.         E[a].pb(b), E[b].pb(a);
  67.     }
  68.     dfs(1,0,1);
  69.     f(j,1,17) f(i,1,N) L[i][j] = L[L[i][j-1]][j-1];
  70.     cin >> Q;
  71.     while(Q--)
  72.     {
  73.         int a,b;
  74.         scanf("%d %d", &a, &b);
  75.         int l = lca(a,b);
  76.         int d1 = D[a] - D[l];
  77.         int d2 = D[b] - D[l];
  78.         if(d1 == d2)
  79.         {
  80.             int node1 = get(a,d1-1);
  81.             int node2 = get(b,d2-1);
  82.             printf("%d\n", N - Size[node1] - Size[node2]);
  83.         }
  84.         else if(d1%2 == d2%2)
  85.         {
  86.             int dist = (d1+d2) / 2;
  87.             if(d1 > d2)
  88.             {
  89.                 int node = get(a,dist);
  90.                 int child = get(a,dist-1);
  91.                 printf("%d\n", Size[node] - Size[child]);
  92.             }
  93.             else
  94.             {
  95.                 int node = get(b,dist);
  96.                 int child = get(b,dist-1);
  97.                 printf("%d\n", Size[node] - Size[child]);
  98.             }
  99.         }
  100.         else printf("0\n");
  101.     }
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement