fork download
copy 
  1. #include<bits/stdc++.h> 
  2. using namespace std; 
  3.  
  4. const long long MaxN = 1e5 + 5, LOG = 17; 
  5.  
  6. long long n,q,par[MaxN][LOG],d[MaxN],sz[MaxN];
  7. vector<long long> vt[MaxN];
  8.  
  9. void dfs(long long u) 
  10. { 
  11.     sz[u] = 1;
  12.  
  13.     for(long long v : vt[u]) 
  14.     { 
  15.         if(v != par[u][0]) 
  16.         { 
  17.             par[v][0] = u; 
  18.             d[v] = d[u] + 1; 
  19.             dfs(v); 
  20.             sz[u] += sz[v]; 
  21.         } 
  22.     } 
  23. } 
  24.  
  25. long long lca(long long u,long long v) 
  26. { 
  27.     if(d[u] < d[v]) swap(u,v); 
  28.  
  29.     for(long long i = LOG-1; i >= 0; i--) 
  30.     { 
  31.         if(d[par[u][i]] >= d[v]) 
  32.         { 
  33.             u = par[u][i]; 
  34.         } 
  35.     } 
  36.  
  37.     if(u == v) return u; 
  38.  
  39.     for(long long i = LOG-1; i >= 0; i--) 
  40.     { 
  41.         if(par[u][i] != par[v][i]) 
  42.         { 
  43.             u = par[u][i]; 
  44.             v = par[v][i]; 
  45.         } 
  46.     } 
  47.  
  48.     return par[u][0]; 
  49. } 
  50.  
  51. void input() 
  52. { 
  53.     cin >> n >> q; 
  54.  
  55.     for(long long i = 1; i < n; i++) 
  56.     { 
  57.         long long u,v; 
  58.         cin >> u >> v; 
  59.  
  60.         vt[u].push_back(v); 
  61.         vt[v].push_back(u); 
  62.     } 
  63. } 
  64.  
  65. void solve() 
  66. { 
  67.     dfs(1); 
  68.  
  69.     for(long long j = 1; j < LOG; j++) 
  70.     { 
  71.         for(long long i = 1; i <= n; i++) 
  72.         { 
  73.             par[i][j] = par[par[i][j-1]][j-1]; 
  74.         } 
  75.     } 
  76.  
  77.     d[0] = -1; 
  78.  
  79.     for(long long i = 1; i <= q; i++) 
  80.     { 
  81.         long long u,v; 
  82.         cin >> u >> v; 
  83.  
  84.         long long l = lca(u,v); 
  85.  
  86.         long long len1 = d[u] - d[l]; 
  87.         long long len2 = d[v] - d[l]; 
  88.         long long len = d[u] + d[v] - 2*d[l]; 
  89.  
  90.         if(len % 2 != 0) 
  91.         { 
  92.             cout << 0 << "\n"; 
  93.         } 
  94.         else if(u == v) 
  95.         { 
  96.             cout << n << "\n"; 
  97.         } 
  98.         else if(len1 == 0 || len2 == 0) 
  99.         { 
  100.             if(len1 == 0) 
  101.             { 
  102.                 long long x = len/2 - 1; 
  103.  
  104.                 for(long long i = 0; i < LOG; i++) 
  105.                 { 
  106.                     if((x >> i) & 1) 
  107.                     { 
  108.                         v = par[v][i]; 
  109.                     } 
  110.                 } 
  111.  
  112.                 cout << sz[par[v][0]] - sz[v] << "\n"; 
  113.             } 
  114.             else 
  115.             { 
  116.                 long long x = len/2 - 1; 
  117.  
  118.                 for(long long i = 0; i < LOG; i++) 
  119.                 { 
  120.                     if((x >> i) & 1) 
  121.                     { 
  122.                         u = par[u][i]; 
  123.                     } 
  124.                 } 
  125.  
  126.                 cout << sz[par[u][0]] - sz[u] << "\n"; 
  127.             } 
  128.         } 
  129.         else 
  130.         { 
  131.             if(d[u] == d[v]) 
  132.             { 
  133.                 long long x = len/2 - 1; 
  134.  
  135.                 for(long long i = 0; i < LOG; i++) 
  136.                 { 
  137.                     if((x >> i) & 1) 
  138.                     { 
  139.                         u = par[u][i]; 
  140.                     } 
  141.                 } 
  142.  
  143.                 for(long long i = 0; i < LOG; i++) 
  144.                 { 
  145.                     if((x >> i) & 1) 
  146.                     { 
  147.                         v = par[v][i]; 
  148.                     } 
  149.                 } 
  150.  
  151.                 cout << n - sz[u] - sz[v] << "\n"; 
  152.             } 
  153.             else 
  154.             { 
  155.                 if(d[u] > d[v]) 
  156.                 { 
  157.                     long long x = len/2 - 1; 
  158.  
  159.                     for(long long i = 0; i < LOG; i++) 
  160.                     { 
  161.                         if((x >> i) & 1) 
  162.                         { 
  163.                             u = par[u][i]; 
  164.                         } 
  165.                     } 
  166.  
  167.                     cout << sz[par[u][0]] - sz[u] << "\n"; 
  168.                 } 
  169.                 else 
  170.                 { 
  171.                     long long x = len/2 - 1; 
  172.  
  173.                     for(long long i = 0; i < LOG; i++) 
  174.                     { 
  175.                         if((x >> i) & 1) 
  176.                         { 
  177.                             v = par[v][i]; 
  178.                         } 
  179.                     } 
  180.  
  181.                     cout << sz[par[v][0]] - sz[v] << "\n"; 
  182.                 } 
  183.             } 
  184.         } 
  185.     } 
  186. } 
  187.  
  188. int main() 
  189. { 
  190.     input(); 
  191.     solve(); 
  192. }
Success #stdin #stdout 0.01s 8432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YiZZLG
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!