SHARE
TWEET

Untitled

a guest Sep 23rd, 2018 122 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define endl '\n'
  3. #define maxn 100010
  4. using namespace std;
  5.  
  6. vector < int > adj[maxn];
  7.  
  8. bool visited[maxn];
  9.  
  10. int n;
  11.  
  12. int dfs(int actual , int destino , int dist)
  13. {
  14.     visited[actual] = true;
  15.  
  16.     int ret = 0;
  17.  
  18.     if(actual == destino)
  19.     {
  20.         return dist;
  21.     }
  22.  
  23.     for(int i = 0; i < adj[actual].size(); i++)
  24.     {
  25.         if(!visited[adj[actual][i]])
  26.         {
  27.             ret = max(dfs(adj[actual][i] , destino , dist + 1) , ret);
  28.         }
  29.     }
  30.  
  31.     visited[actual] = false;
  32.  
  33.     return ret;
  34. }
  35.  
  36. void clean()
  37. {
  38.     memset(visited , false , sizeof(visited));
  39. }
  40.  
  41.  
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(false);
  45.     cin.tie(nullptr);
  46.     cout.tie(nullptr);
  47.     cout.precision(10);
  48.  
  49.     //freopen("in.txt" , "r" , stdin);
  50.  
  51.     int q , a , b , c , d;
  52.  
  53.     cin >> n >> q;
  54.  
  55.     while(--n)
  56.     {
  57.         cin >> a >> b;
  58.  
  59.         adj[a].emplace_back(b);
  60.         adj[b].emplace_back(a);
  61.     }
  62.  
  63.     while(q--)
  64.     {
  65.         cin >> a >> b >> c >> d;
  66.  
  67.         clean();
  68.  
  69.         int x = dfs(a , b , 0);
  70.  
  71.         clean();
  72.  
  73.         x += dfs(c , d , 0);
  74.  
  75.         clean();
  76.  
  77.         int sumy1 = dfs(a , c , 0);
  78.  
  79.         clean();
  80.  
  81.         sumy1 += dfs(b , d , 0);
  82.  
  83.         clean();
  84.  
  85.         int sumy2 = dfs(a , d , 0);
  86.  
  87.         clean();
  88.  
  89.         sumy2 += dfs(b , c , 0);
  90.  
  91.         int y = min(sumy1 , sumy2);
  92.  
  93.         if(y > x)
  94.         {
  95.             cout << 0 << endl;
  96.         }
  97.         else
  98.         {
  99.             cout << (x - y) / 2 + 1 << endl;
  100.         }
  101.  
  102.     }
  103.  
  104.     return 0;
  105. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top