/* * Problem link * http://yukicoder.me/problems/1024 */ /*門松を許すな!!!!!!!!!!!!!!!!!!!!!*/ #include using namespace std; struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init; #define rep(i,n) for(auto i=(n)*0;i V; typedef vector VV; typedef vector E; typedef vector Graph; bool checkKadomatsu(int a, int b, int c) { return (a != c) ? ((a > b&&b < c) || (ac)) : false; } void make_tree(int v, Graph &G, VV &PP, V &D, V &A, V &prev, V& len) { range(u, G[v]) { if (u != PP[0][v]) { D[u] = D[v] + 1; PP[0][u] = v; prev[u] = A[v]; if (checkKadomatsu(prev[v],A[v],A[u])) len[u] = len[v] + 1; else len[u] = (A[v] != A[u]); make_tree(u, G, PP, D, A, prev, len); } } } void build_PP(VV &PP) { int N = PP[0].size(); for (int k = 0, f = 1; f; k++) { f = 0; rep(i,N) if (PP[k][i] >= 0) PP[k + 1][i] = PP[k][PP[k][i]],f = 1; } } int lca(int u, int v, V &D, VV &PP) { if (D[u] > D[v])swap(u, v); for (int k = 0, d; (d = D[v] - D[u]); k++) if ((d >> k) & 1)v = PP[k][v]; if (u == v)return v; for (int k = PP.size() - 1; k >= 0; k--) if (PP[k][u] != PP[k][v]) u = PP[k][u], v = PP[k][v]; return PP[0][u]; } int underroot(int root, int v, V &D, VV &PP) { int sz = D[v] - D[root] - 1; for (int k = 0; sz; k++, sz >>= 1) { if (sz & 1)v = PP[k][v]; } return v; } int main() { #ifdef INPUT_FROM_FILE ifstream cin("sample.in"); ofstream cout("sample.out"); #endif int N, Q; while (cin >> N) { V A(N); range(it, A)cin >> it; Graph g(N); rep(i, N - 1) { int x, y; cin >> x >> y; x--; y--; g[x].push_back(y); g[y].push_back(x); } V depth(N, 0), len(N), prev(N); VV parent(30, V(N, -1)); len[0] = 0; prev[0] = A[0]; make_tree(0, g, parent, depth, A, prev, len); build_PP(parent); cin >> Q; while (Q--) { int u, v, pu, pv; cin >> u >> v; u--; v--; if (depth[u] > depth[v]) swap(u, v); int root = lca(u, v, depth, parent); int l = depth[v] - depth[u]; if (root == u) { if (l > len[v] || l % 2 == 0 || l < 3) { cout << "NO" << endl; continue; } pu = underroot(u, v, depth, parent); pv = parent[0][v]; if (!checkKadomatsu(A[pu], A[u], A[v])) { cout << "NO" << endl; continue; } if (!checkKadomatsu(A[pv], A[v], A[u])) { cout << "NO" << endl; continue; } cout << "YES" << endl; } else { int lu = depth[u] - depth[root]; int lv = depth[v] - depth[root]; if (lu > len[u] || lv > len[v] || (lu + lv) % 2 == 0 || (lu + lv) < 3) { cout << "NO" << endl; continue; } pu = parent[0][u]; pv = parent[0][v]; if(!checkKadomatsu(A[pu],A[u],A[v])) { cout << "NO" << endl; continue; } if (!checkKadomatsu(A[pv], A[v], A[u])) { cout << "NO" << endl; continue; } pv = underroot(root, v, depth, parent); pu = underroot(root, u, depth, parent); if (!checkKadomatsu(A[pu], A[root], A[pv])) { cout << "NO" << endl; continue; } cout << "YES" << endl; } } } return 0; }