package yukicoder; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().solve(); // int c = 0; // while (true) { // new Q363().build(); // String s1 = new Q363().solve_trial(); // String s2 = ""; // try { // s2 = new sample().run(N, A, X, Y); // } catch (Exception e) { // // TODO 自動生成された catch ブロック // e.printStackTrace(); // } // c++; // if (!s1.equals(s2)) { // System.out.println(N); // for (int i = 0; i < N; i++) { // System.out.print(A[i] + " "); // } // System.out.println(); // for (int i = 0; i < N - 1; i++) { // System.out.println(X[i] + " " + Y[i]); // } // System.out.println(s1 + " " + s2); // break; // } // } // System.out.println("試行回数" + c); } ArrayList edges[]; 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"); } } } } String solve_trial() { 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 = X[i] - 1; int y = Y[i] - 1; edges[x].add(y); edges[y].add(x); } init(N); init2(); int Q = 1; for (int i = 0; i < Q; i++) { int u = 1 - 1; int v = 2 - 1; int lca = lca(u, v); chi.clear(); if (!isKado_seq(u, lca)) { return "NO"; } else if (!isKado_seq(v, lca)) { return "NO"; } else if (v != lca && !isKado(A[u], A[v], A[parent[0][v]])) { return "NO"; } else if (u != lca && !isKado(A[v], A[u], A[parent[0][u]])) { return "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)])) { return "NO"; } else { return "YES"; } } } return "Error"; } 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 (parent[v][k]==-1) continue; C[v + 1][k] = C[v][k] & C[v][parent[v][k]]; } } } 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) { int judge = C[i][c]; if (judge == 0) { return false; } c = parent[i][c]; if (C[0][c] == 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(); static int N; static int[] A; static int[] X; static int[] Y; void build() { int max = 4; N = (int) (Math.random() * max) + 3;// 頂点数 A = new int[N]; X = new int[N - 1]; Y = new int[N - 1]; for (int i = 0; i < N; i++) { A[i] = (int) (Math.random() * 10) + 1; } DJSet ds = new DJSet(N); // 0-indexedで接続されている頂点を表示 int count = 0; while (ds.count() != 1) { int x = (int) (Math.random() * N); int y = (int) (Math.random() * N); if (ds.equiv(x, y)) continue; else { X[count] = x + 1; Y[count] = y + 1; count++; ds.setUnion(x, y); } } } class DJSet { int n;// the number of vertices int[] d; DJSet(int n) { this.n = n; d = new int[n]; Arrays.fill(d, -1); } int root(int x) { return d[x] < 0 ? x : root(d[x]); } boolean setUnion(int x, int y) { x = root(x); y = root(y); if (x != y) { if (x < y) { int d = x; x = y; y = d; } // x>y d[y] += d[x]; d[x] = y; } return x != y; } boolean equiv(int x, int y) { return root(x) == root(y); } // xを含む木のNodeの数 int size(int x) { return d[root(x)] * (-1); } // 連結グラフの数 int count() { int ct = 0; for (int u : d) { if (u < 0) ct++; } return ct; } } }