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