Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Nguyen Huu Hoang Minh
- #include <bits/stdc++.h>
- #define sz(x) int(x.size())
- #define all(x) x.begin(),x.end()
- #define reset(x) memset(x, 0,sizeof(x))
- #define pb push_back
- #define mp make_pair
- #define fi first
- #define se second
- #define N 100005
- #define remain(x) if (x > MOD) x -= MOD
- #define ii pair<int, int>
- #define iiii pair< ii , ii >
- #define viiii vector< iiii >
- #define vi vector<int>
- #define vii vector< ii >
- #define bit(x, i) (((x) >> (i)) & 1)
- #define Task "test"
- #define int long long
- using namespace std;
- typedef long double ld;
- const int inf = 1e10;
- const int minf = -1e10;
- const int logN = log2(N)+1;
- int n;
- vector<int> a[N];
- int d[N];
- int f[N][logN];
- void readfile()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(0);cout.tie(0);
- if (fopen(Task".inp","r"))
- {
- freopen(Task".inp","r",stdin);
- //freopen(Task".out","w",stdout);
- }
- cin >> n;
- for(int i=1; i<n; i++)
- {
- int u, v;
- cin >> u >> v;
- a[u].pb(v);
- a[v].pb(u);
- }
- }
- void dfs(int u)
- {
- for(int i=1; i<logN; i++)
- f[u][i] = f[f[u][i-1]][i-1];
- for(int v : a[u])
- {
- if (!d[v] && v!=1)
- {
- f[v][0] = u;
- d[v] = d[u] + 1;
- dfs(v);
- }
- }
- }
- int lca(int u, int v)
- {
- if (d[u] < d[v]) swap(u,v);
- int del = d[u]-d[v];
- for(int i=log2(del); i>=0; i--)
- {
- if ((del>>i)&1) u = f[u][i];
- }
- if (u==v) return u;
- for(int i=logN-1; i>=0; i--)
- {
- if (f[u][i] != f[v][i])
- {
- u = f[u][i];
- v = f[v][i];
- }
- }
- return f[u][0];
- }
- void preproc()
- {
- dfs(1);
- }
- int len(int u, int v)
- {
- int w = lca(u,v);
- return (d[u] + d[v] - 2*d[w]);
- }
- void proc()
- {
- int t;
- cin >> t;
- while (t--)
- {
- int u, v, x, y, k;
- int res = INT_MAX;
- cin >> u >> v >> x >> y >> k;
- int len1 = len(x,y);
- int len2 = len(x,u)+len(v,y)+1;
- int len3 = len(x,v)+len(u,y)+1;
- if (len1%2 == k%2) res = min(res,len1);
- if (len2%2 == k%2) res = min(res,len2);
- if (len3%2 == k%2) res = min(res,len3);
- if (res <= k) cout << "YES \n";
- else cout << "NO \n";
- }
- }
- signed main()
- {
- readfile();
- preproc();
- proc();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement