#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; class LowestCommonAncestor { private: vector > to; vector depth; public: LowestCommonAncestor() {} LowestCommonAncestor(const vector >& edges, int root) { int n = edges.size(); to.assign(n, vector()); depth.resize(n); stack > stk; stk.push(make_tuple(root, -1, 0, 0)); while(!stk.empty()){ int curr, prev, cnt, i; tie(curr, prev, cnt, i) = stk.top(); stk.pop(); if(i == 0){ depth[curr] = cnt; if(prev != -1){ to[curr].push_back(prev); int j = prev; for(unsigned k=0; k 0){ if(dist % 2 == 1) curr = to[curr][i]; dist /= 2; ++ i; } return curr; } // 2つのノードの最小共通祖先を取得 int getAncestor(int a, int b) { int diff = depth[a] - depth[b]; if(diff < 0) b = climb(b, -diff); else a = climb(a, diff); if(a == b) return a; for(int i=to[a].size()-1; i>=0; --i){ if(i < (int)to[a].size() && to[a][i] != to[b][i]){ a = to[a][i]; b = to[b][i]; } } return to[a][0]; } // ノードの深さを取得 int getDepth(int a) { return depth[a]; } // 2つのノードの距離を取得 int getDist(int a, int b) { int c = getAncestor(a, b); return getDepth(a) + getDepth(b) - getDepth(c) * 2; } }; bool checkKadomatsu(const vector& a) { if(a[0] == a[2]) return false; return (a[0] < a[1] && a[2] < a[1]) || (a[0] > a[1] && a[2] > a[1]); } int n; vector a; vector > edges; vector cnt; LowestCommonAncestor lca; void dfs(int curr, int prev, int prev2) { if(prev2 != -1 && checkKadomatsu({a[curr], a[prev], a[prev2]})) cnt[curr] = cnt[prev] + 1; for(int next : edges[curr]){ if(next != prev) dfs(next, curr, prev); } } bool solve(int u, int v) { if(lca.getDist(u, v) < 2) return false; int w = lca.getAncestor(u, v); int du = lca.getDist(u, w); int dv = lca.getDist(v, w); if(u == w || v == w){ if(u == w){ swap(u, v); swap(du, dv); } int u2 = lca.climb(u, du - 1); if(cnt[u] - cnt[u2] < du - 1) return false; int u3 = lca.climb(u, 1); return checkKadomatsu({a[u3], a[u], a[v]}) && checkKadomatsu({a[u], a[v], a[u2]}); } else{ int u2 = lca.climb(u, du - 1); if(cnt[u] - cnt[u2] < du - 1) return false; int v2 = lca.climb(v, dv - 1); if(cnt[v] - cnt[v2] < dv - 1) return false; if(!checkKadomatsu({a[u2], a[w], a[v2]})) return false; int u3 = lca.climb(u, 1); int v3 = lca.climb(v, 1); return checkKadomatsu({a[u3], a[u], a[v]}) && checkKadomatsu({a[u], a[v], a[v3]}); } } int main() { cin >> n; a.resize(n); for(int i=0; i> a[i]; edges.assign(n, vector()); for(int i=0; i> x >> y; -- x; -- y; edges[x].push_back(y); edges[y].push_back(x); } lca = LowestCommonAncestor(edges, 0); cnt.assign(n, 0); dfs(0, -1, -1); int q; cin >> q; while(--q >= 0){ int u, v; cin >> u >> v; -- u; -- v; if(solve(u, v)) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }