package yukicoder; import java.util.ArrayList; import java.util.Scanner; public class Main{ public static void main(String[] args) { new Main().solve(); } ArrayList edges[]; int[] A; void solve() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); A = new int[N]; for (int i = 0; i < N; i++) A[i] = sc.nextInt(); edges = new ArrayList[N]; for (int i = 0; i < N; i++) edges[i] = new ArrayList(); for (int i = 0; i < N - 1; i++) { int x = sc.nextInt() - 1; int y = sc.nextInt() - 1; edges[x].add(y); edges[y].add(x); } init(N); init2(); int Q = sc.nextInt(); for (int i = 0; i < Q; i++) { int u = sc.nextInt() - 1; int v = sc.nextInt() - 1; int lca = lca(u, v); chi.clear(); if(!isKado_seq(u,lca)){ System.out.println("NO"); } else if(!isKado_seq(v,lca)){ System.out.println("NO"); } else if(v!=lca&&!isKado(A[u],A[v],A[parent[0][v]])){ System.out.println("NO"); } else if(u!=lca&&!isKado(A[v],A[u],A[parent[0][u]])){ System.out.println("NO"); }else { if(chi.size()==1){ if(lca!=u)chi.add(u); else if(lca!=v)chi.add(v); else throw new AssertionError("lcaの一方のみがuかvであるはず"); } if(!isKado(A[chi.get(0)],A[lca],A[chi.get(1)])){ System.out.println("NO"); }else{ System.out.println("YES"); } } } } boolean isKado(int a, int b, int c) { if (a < 0 || b < 0 || c < 0) return false; if (a == b || b == c || c == a) return false; if (a < b && b > c) return true; if (a > b && b < c) return true; return false; } int MAX_LOG_V;// =(int)log2(MAX_V)+1 int MAX_V; int root;// 根ノードの番号 int parent[][];// [MAX_LOG_V + 1][MAX_V] // parent[k][v] 2^k回親を辿ったときに到達する頂点(根を通り過ぎたときは-1) int[] depth;// [MAX_V] 根からの深さ void init(int N) { // 変数の用意 MAX_V = N; MAX_LOG_V = (int) (Math.log(MAX_V) / Math.log(2)) + 1; root = 0; parent = new int[MAX_LOG_V + 1][MAX_V]; depth = new int[MAX_V]; // parent[0]とdepthを初期化する dfs(root, -1, 0); // parentを初期化する for (int k = 0; k < MAX_LOG_V; k++) { for (int v = 0; v < MAX_V; v++) { if (parent[k][v] < 0) { parent[k + 1][v] = -1; } else { parent[k + 1][v] = parent[k][parent[k][v]]; } } } } void dfs(int v, int p, int d) { parent[0][v] = p; depth[v] = d; for (int i = 0; i < edges[v].size(); i++) { if (edges[v].get(i) != p) dfs(edges[v].get(i), v, d + 1); } } int lca(int u, int v) { // uとvの深さが同じになるまで親を辿る if (depth[u] > depth[v]) { int d = u; u = v; v = d; } // depth[v]-depth[u]>=2^kとなる最小のkを求める。 // つまりuをvと深さが同じか小さいぎりぎりのところまで親を辿る。 for (int k = 0; k < MAX_LOG_V; k++) { if ((((depth[v] - depth[u]) >> k) & 1) == 1) { v = parent[k][v]; } } if (u == v) return u; // uとvが衝突しないように辿る。 for (int k = MAX_LOG_V - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v] && parent[k][u] != -1 && parent[k][v] != -1) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } /* * B[k]=1ならば A[k],A[k+1],A[k+2]が門松列であり、0なら門松列でない、とする。 * B[k]=1&&B[k+1]=1のときのみ、A[k],A[k+1],A[k+2],A[k+3]が門松列 * B[k]=1&&B[k+1]=1かつB[k+2]=1&&B[k+3]=1ならばA[k],A[k+1],A[k+2],A[k+3],A[k+4],A * [k+5]が門松列。 * C[0][k]=B[k] * C[1][k]=C[0][[k]&C[0][k+1] * C[2][k]=C[1][k]&C[1][k+2] * C[3][k]=C[2][k]&C[2][k+4] * C[4][k]=C[3][k]&C[3][k+8] * C[v][k]=C[v-1][k]&C[v-1][k+2^(v-1)] と次々に定義する。 このとき、C[v][k]=1であることと * A[k],...,A[k+2^v+2] が門松列であることは同値である。 */ int[][] C; void init2() { // 変数の用意 C = new int[MAX_LOG_V + 1][MAX_V]; // C[0]を初期化する for (int i = 0; i < MAX_V; i++) { int p1 = parent[0][i]; if(p1==-1)continue; int p2 = parent[0][p1]; if(p2==-1)continue; if (isKado(A[i], A[p1], A[p2])) { C[0][i] = 1; } } // Cを初期化する for (int v = 0; v < MAX_LOG_V; v++) { for (int k = 0; k < MAX_V; k++) { if((k + (int) Math.pow(2, v))>=MAX_V)continue; C[v + 1][k] = C[v][k] & C[v][k + (int) Math.pow(2, v)]; } } } boolean isKado_seq(int c, int p) { int d = depth[c] - (depth[p] + 2); if (d == -1) { chi.add(c); return true; } if(d==-2){ return true; } if (C[0][c] == 0) return false; for (int i = 0; d > 0; d >>= 1, i++) { if ((d & 1) == 1) { c = parent[i][c]; int judge = C[i][c]; if (judge == 0) return false; } } if (parent[0][parent[0][c]] != p) throw new AssertionError("c!=p"); chi.add(parent[0][c]); return true; } ArrayList chi = new ArrayList(); }