#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector vi; typedef pair pii; typedef vector > vpii; typedef long long ll; template inline void amin(T &x, U y) { if(y < x) x = y; } template inline void amax(T &x, U y) { if(x < y) x = y; } class FastInput { bool _end; public: FastInput() : _end(false) {} operator void*() { return _end ? 0 : (void*)this; } template void read_unsigned(T *res) { T x = 0; for(char c = skip(); '0' <= c && c <= '9'; c = gc()) x = x * 10 + (c - '0'); *res = x; } template void read_signed(T *res) { char c = skip(); bool sign = false; if(c == '-') sign = true, c = gc(); T x = 0; for(; '0' <= c && c <= '9'; c = gc()) x = x * 10 + (c - '0'); *res = !sign ? x : -x; } void read_c_string(char *str, int *len) { int n = 0; for(char c = skip(); !is_delim(c); c = gc()) str[n ++] = c; str[n] = 0; *len = n; } void read_string(std::string *str) { str->clear(); for(char c = skip(); !is_delim(c); c = gc()) *str += c; } void read_line(std::string *str) { str->clear(); for(char c = gc(); c != '\n'; c = gc()) *str += c; if(!str->empty() && (*str)[str->size() - 1] == '\r') str->resize(str->size() - 1); } void read_double(double *res) { std::string buf; read_string(&buf); sscanf(buf.c_str(), "%lf", res); } void read_char(char *res) { *res = skip(); } void read_string_buf(char *res, int n) { *res = skip(); } FastInput &operator()(char &res) { read_char(&res); return *this; } FastInput &operator()(int &res) { read_signed(&res); return *this; } FastInput &operator()(unsigned &res) { read_unsigned(&res); return *this; } FastInput &operator()(long long &res) { read_signed(&res); return *this; } FastInput &operator()(unsigned long long &res) { read_unsigned(&res); return *this; } FastInput &operator()(char *res) { int len; read_c_string(res, &len); return *this; } FastInput &operator()(std::string &res) { read_string(&res); return *this; } FastInput &operator()(double &res) { read_double(&res); return *this; } template FastInput &operator()(T1 &res1, T2 &res2) { return operator()(res1)(res2); } template FastInput &operator()(T1 &res1, T2 &res2, T3 &res3) { return operator()(res1)(res2)(res3); } template FastInput &a(T *a, int n) { for(int i = 0; i < n; ++ i) operator()(a[i]); return *this; } template FastInput &operator()(vector &v) { for(size_t i = 0; i < v.size(); ++ i) operator()(v[i]); return *this; } private: static char gc() { #if defined(__GNUC__) && !defined(__MINGW32__) return (char)getchar_unlocked(); #elif defined(_MSC_VER) return (char)_getchar_nolock(); #else return (char)getchar(); #endif } static bool is_delim(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == EOF; } char skip() { if(_end) return EOF; char c; for(c = gc(); c != -1 && is_delim(c); c = gc()); if(c == EOF) _end = true; return c; } } in; class FastOutput { public: template void print_unsigned(T x) { char buf[24]; int n = 0; do buf[n ++] = x % 10, x /= 10; while(x != 0); while(n > 0) pc('0' + buf[-- n]); } template void print_signed(T x) { char buf[24]; int n = 0; bool sign = false; if(x < 0) sign = true; //depends on the -x % y behaviour do buf[n ++] = x % 10, x /= 10; while(x != 0); if(!sign) { while(n > 0) pc('0' + buf[-- n]); } else { pc('-'); while(n > 0) pc('0' - buf[-- n]); } } void print_c_string(const char *str) { for(const char *p = str; *p; ++ p) pc(*p); } void print_string(const std::string &str) { print_c_string(str.c_str()); } void print_double(double x, int digits) { //|res| < 2^1024 ~ 10^308 char buf[512]; #ifdef _MSC_VER sprintf_s(buf, "%.*f", digits, x); #else sprintf(buf, "%.*f", digits, x); #endif print_c_string(buf); } void print_char(char x) { pc(x); } FastOutput &operator()(char x) { print_char(x); return *this; } FastOutput &operator()(int x) { print_signed(x); return *this; } FastOutput &operator()(unsigned x) { print_unsigned(x); return *this; } FastOutput &operator()(long long x) { print_signed(x); return *this; } FastOutput &operator()(unsigned long long x) { print_unsigned(x); return *this; } FastOutput &operator()(const char *str) { print_c_string(str); return *this; } FastOutput &operator()(const std::string &str) { print_string(str); return *this; } FastOutput &operator()(double x) { print_double(x, 10); return *this; } template FastOutput &operator()(T1 x1, T2 x2) { return operator()(x1)(x2); } template FastOutput &operator()(T1 x1, T2 x2, T3 x3) { return operator()(x1)(x2)(x3); } template FastOutput &operator()(T1 x1, T2 x2, T3 x3, T4 x4) { return operator()(x1)(x2)(x3)(x4); } private: static void pc(char c) { #if defined(__GNUC__) && !defined(__MINGW32__) putchar_unlocked(c); #elif defined(_MSC_VER) _putchar_nolock(c); #else putchar(c); #endif } } out; class FastOutputN { public: template FastOutputN &operator()(T1 x1) { out(x1)('\n'); return *this; } template FastOutputN &operator()(T1 x1, T2 x2) { out(x1, x2)('\n'); return *this; } template FastOutputN &operator()(T1 x1, T2 x2, T3 x3) { out(x1, x2, x3)('\n'); return *this; } template FastOutputN &operator()(T1 x1, T2 x2, T3 x3, T4 x4) { out(x1, x2, x3, x4)('\n'); return *this; } template FastOutputN &a(const T *a, int n) { for(int i = 0; i < n; ++ i) { if(i != 0) out(' '); out(a[i]); } out('\n'); return *this; } template FastOutputN &operator()(const vector &v) { for(size_t i = 0; i < v.size(); ++ i) { if(i != 0) out(' '); out(v[i]); } out('\n'); return *this; } } outn; class SchieberVishkinLCA { public: typedef unsigned Word; typedef int Vertex; private: static inline Word lowestOneBit(Word v) { return v & (~v + 1); } static inline Word highestOneBitMask(Word v) { v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return v >> 1; } std::vector indices; //Vertex -> index std::vector maxHIndices; //Vertex -> index std::vector ancestorHeights; //Vertex -> Word std::vector pathParents; //index-1 -> Vertex public: void build(const std::vector &preorder, const std::vector &parents, Vertex root) { Vertex N = static_cast(preorder.size()); ancestorHeights.resize(N); maxHIndices.resize(N); indices.resize(N); pathParents.resize(N); for(Vertex ix = 0; ix < N; ++ ix) indices[preorder[ix]] = ix + 1; for(Vertex i = 0; i < N; ++ i) maxHIndices[i] = indices[i]; for(Vertex ix = N - 1; ix > 0; -- ix) { Vertex v = preorder[ix], parent = parents[v]; if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v])) maxHIndices[parent] = maxHIndices[v]; } ancestorHeights[root] = 0; for(Vertex ix = 1; ix < N; ++ ix) { Vertex v = preorder[ix], parent = parents[v]; ancestorHeights[v] = ancestorHeights[parent] | lowestOneBit(maxHIndices[v]); } pathParents[0] = root; for(Vertex ix = 1; ix < N; ++ ix) { Vertex v = preorder[ix], parent = parents[v]; if(maxHIndices[v] != maxHIndices[parent]) pathParents[indices[v] - 1] = parent; else pathParents[indices[v] - 1] = pathParents[indices[parent] - 1]; } } Vertex query(Vertex v, Vertex u) const { Word Iv = maxHIndices[v], Iu = maxHIndices[u]; Word hIv = lowestOneBit(Iv), hIu = lowestOneBit(Iu); Word hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu); Word j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask); Vertex x, y; if(j == hIv) x = v; else { Word kMask = highestOneBitMask(ancestorHeights[v] & (j - 1)); x = pathParents[(indices[v] & ~kMask | (kMask + 1)) - 1]; } if(j == hIu) y = u; else { Word kMask = highestOneBitMask(ancestorHeights[u] & (j - 1)); y = pathParents[(indices[u] & ~kMask | (kMask + 1)) - 1]; } return indices[x] < indices[y] ? x : y; } }; vector t_parent; vi t_ord; void tree_getorder(const vector &g, int root) { int n = g.size(); t_parent.assign(n, -1); t_ord.clear(); vector stk; stk.push_back(root); while(!stk.empty()) { int i = stk.back(); stk.pop_back(); t_ord.push_back(i); for(int j = (int)g[i].size() - 1; j >= 0; j --) { int c = g[i][j]; if(t_parent[c] == -1 && c != root) stk.push_back(c); else t_parent[i] = c; } } } bool isok(int a, int b, int c) { return a != c && ((a < b && b > c) || (a > b && b < c)); } struct LevelAncestorQuery { int depth, i; }; void batchedLevelAncestorQueries(int i, int p, const vector &g, vi &path, const vector> &queries, vector &res) { path.push_back(i); for(const LevelAncestorQuery &q : queries[i]) res[q.i] = (int)path.size() <= q.depth ? -1 : path[q.depth]; for(int j : g[i]) if(j != p) batchedLevelAncestorQueries(j, i, g, path, queries, res); path.pop_back(); } int main() { int N; while(in(N)) { vector A(N); in(A); vector > g(N); for(int i = 0; i < N - 1; ++ i) { int u, v; in(u, v), -- u, -- v; g[u].push_back(v); g[v].push_back(u); } tree_getorder(g, 0); vector parok(N); for(int ix = 0; ix < (int)t_ord.size(); ++ ix) { int i = t_ord[ix], p = t_parent[i]; parok[i] = p == -1 || p == 0 || isok(A[t_parent[p]], A[p], A[i]); } vector okcnt(N), depth(N); okcnt[0] = 1; for(int ix = 1; ix < (int)t_ord.size(); ++ ix) { int i = t_ord[ix], p = t_parent[i]; okcnt[i] = okcnt[p] + parok[i]; depth[i] = depth[p] + 1; } SchieberVishkinLCA lca; lca.build(t_ord, t_parent, 0); int Q; in(Q); vector> queries(Q); vector ws(Q); vector> laqueries(N); rep(qi, Q) { int u; int v; in(u, v), -- u, -- v; queries[qi] = { u, v }; } vector ans(Q, true); rep(qi, Q) { int u, v; tie(u, v) = queries[qi]; int w = lca.query(u, v); ws[qi] = w; int len = depth[u] + depth[v] - depth[w] * 2 + 1; if(len <= 2) { ans[qi] = false; } else { if(u != w) laqueries[u].push_back(LevelAncestorQuery{ depth[w] + 1, qi * 2 + 0 }); if(v != w) laqueries[v].push_back(LevelAncestorQuery{ depth[w] + 1, qi * 2 + 1 }); } } vector cs(Q * 2, -1); { vector path; batchedLevelAncestorQueries(0, -1, g, path, laqueries, cs); } rep(qi, Q) { if(ans[qi]) { int u, v; tie(u, v) = queries[qi]; int w = ws[qi]; int num = 0; int cu = cs[qi * 2 + 0], cv = cs[qi * 2 + 1]; //wが真ん中 if(w != u && w != v) { ans[qi] = ans[qi] && isok(A[cu], A[w], A[cv]); num += 1; } //u~w, v~w rep(uv, 2) { int t = uv == 0 ? u : v, a = uv == 0 ? cu : cv; if(t == w) continue; ans[qi] = ans[qi] && okcnt[t] - okcnt[a] == depth[t] - depth[a]; num += depth[t] - depth[a]; } //追加された辺を含むもの rep(uv, 2) { int x = uv == 0 ? u : v, y = uv == 0 ? v : u; int c; if(y == w) { c = uv == 0 ? cu : cv; } else { c = t_parent[y]; } ans[qi] = ans[qi] && isok(A[x], A[y], A[c]); num += 1; } assert(num == depth[u] + depth[v] - depth[w] * 2 + 1); } outn(ans[qi] ? "YES" : "NO"); } } return 0; }