Advertisement
MinhNGUYEN2k4

1tree

Mar 27th, 2021
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.36 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 100005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26. const int logN = log2(N)+1;
  27.  
  28. int n;
  29. vector<int> a[N];
  30. int d[N];
  31. int f[N][logN];
  32.  
  33. void readfile()
  34. {
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(0);cout.tie(0);
  37.     if (fopen(Task".inp","r"))
  38.     {
  39.         freopen(Task".inp","r",stdin);
  40.         //freopen(Task".out","w",stdout);
  41.     }
  42.     cin >> n;
  43.     for(int i=1; i<n; i++)
  44.     {
  45.         int u, v;
  46.         cin >> u >> v;
  47.         a[u].pb(v);
  48.         a[v].pb(u);
  49.     }
  50. }
  51.  
  52. void dfs(int u)
  53. {
  54.     for(int i=1; i<logN; i++)
  55.         f[u][i] = f[f[u][i-1]][i-1];
  56.     for(int v : a[u])
  57.     {
  58.         if (!d[v] && v!=1)
  59.         {
  60.             f[v][0] = u;
  61.             d[v] = d[u] + 1;
  62.             dfs(v);
  63.         }
  64.     }
  65. }
  66.  
  67. int lca(int u, int v)
  68. {
  69.     if (d[u] < d[v]) swap(u,v);
  70.     int del = d[u]-d[v];
  71.     for(int i=log2(del); i>=0; i--)
  72.     {
  73.         if ((del>>i)&1) u = f[u][i];
  74.     }
  75.     if (u==v) return u;
  76.     for(int i=logN-1; i>=0; i--)
  77.     {
  78.         if (f[u][i] != f[v][i])
  79.         {
  80.             u = f[u][i];
  81.             v = f[v][i];
  82.         }
  83.     }
  84.     return f[u][0];
  85. }
  86.  
  87. void preproc()
  88. {
  89.     dfs(1);
  90. }
  91.  
  92. int len(int u, int v)
  93. {
  94.     int w = lca(u,v);
  95.     return (d[u] + d[v] - 2*d[w]);
  96. }
  97.  
  98. void proc()
  99. {
  100.     int t;
  101.     cin >> t;
  102.     while (t--)
  103.     {
  104.         int u, v, x, y, k;
  105.         int res = INT_MAX;
  106.         cin >> u >> v >> x >> y >> k;
  107.         int len1 = len(x,y);
  108.         int len2 = len(x,u)+len(v,y)+1;
  109.         int len3 = len(x,v)+len(u,y)+1;
  110.         if (len1%2 == k%2) res = min(res,len1);
  111.         if (len2%2 == k%2) res = min(res,len2);
  112.         if (len3%2 == k%2) res = min(res,len3);
  113.         if (res <= k) cout << "YES \n";
  114.         else cout << "NO \n";
  115.     }
  116. }
  117.  
  118. signed main()
  119. {
  120.     readfile();
  121.     preproc();
  122.     proc();
  123.     return 0;
  124. }
  125.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement