#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; namespace exstd{ char buff[200000]; class FastInStream{ public: FILE* filePointer; FastInStream(){filePointer = stdin;} FastInStream(FILE* fp){filePointer = fp;} template inline void get(H& h); template inline void get(H& h, T& ... t); }; inline FastInStream& operator >> (FastInStream& is, int& v){ fscanf(is.filePointer, "%d", &v); return is;} inline FastInStream& operator >> (FastInStream& is, long long& v){ fscanf(is.filePointer, "%lld", &v); return is;} inline FastInStream& operator >> (FastInStream& is, double& v){ fscanf(is.filePointer, "%lf", &v); return is;} inline FastInStream& operator >> (FastInStream& is, string& v){ fscanf(is.filePointer, "%s", buff); v = buff; return is;} //inline FastInStream& operator >> (FastInStream& is, __int128& v){v = 0;string s; is >> s;int sgn = 1;int p = 0;if(s[p] == '-'){ sgn=-1; p++;}for(;p FastInStream& operator >> (FastInStream& is, vector& vec){ for(auto& v: vec) is >> v; return is;} template FastInStream& operator , (FastInStream& is, T& v){ return is >> v; } template inline void FastInStream::get(H& h){(*this) >> h;} template inline void FastInStream::get(H& h, T& ... t){ (*this) >> h; FastInStream::get(t...); } struct FastOutEndLine{ int dammy; } fendl; struct FastOutEndLineFlush{ int dammy; } fendlf; class FastOutStream{ public: FILE* filePointer; FastOutStream(){filePointer = stdout;} FastOutStream(FILE* fp){filePointer = fp;} template inline void print(const H& h); template void print(const H& h, const T& ... t); template inline void println(const H& h); template void println(const H& h, const T& ... t); void flush(){fflush(filePointer);} }; inline FastOutStream& operator << (FastOutStream& os, const FastOutEndLine& v){ fprintf(os.filePointer, "\n"); return os; } inline FastOutStream& operator << (FastOutStream& os, const FastOutEndLineFlush& v){ fprintf(os.filePointer, "\n"); fflush(os.filePointer); return os; } inline FastOutStream& operator << (FastOutStream& os, const int& v){ fprintf(os.filePointer, "%d", v); return os; } inline FastOutStream& operator << (FastOutStream& os, const long long& v){ fprintf(os.filePointer, "%lld", v); return os; } inline FastOutStream& operator << (FastOutStream& os, const double& v){ fprintf(os.filePointer, "%.12f", v); return os; } inline FastOutStream& operator << (FastOutStream& os, const string& v){ fprintf(os.filePointer, "%s", v.c_str()); return os; } //FastOutStream& operator << (FastOutStream& os, __int128 v){if(v==0) return os << 0;int sgn = 1;if(v<0){ sgn = -1; v = -v; }string tmp;while(v>0){ tmp.push_back('0' + v%10); v/=10; }if(sgn<0) tmp.push_back('-');reverse(tmp.begin(), tmp.end());return os << tmp;} template FastOutStream& operator << (FastOutStream& os, const vector& vec){ for(int i=0; i inline FastOutStream& operator , (FastOutStream& os, const T& v){ return os << v; } template inline void FastOutStream::print(const H& h){ (*this) << h; } template void FastOutStream::print(const H& h, const T& ... t){ (*this) << h << " "; FastOutStream::print(t...); } template inline void FastOutStream::println(const H& h){ (*this) << h << "\n"; } template void FastOutStream::println(const H& h, const T& ... t){ (*this) << h << " "; FastOutStream::println(t...); } FastInStream fin; FastOutStream fout; FastOutStream ferr(stderr); } using namespace exstd; class HeavyLightDecomposition{ public: struct heavy_set{ vector element; int depth; int parent_vertex; heavy_set(int v, int d, int par) : element(1,v), depth(d), parent_vertex(par){} }; vector>& G; vector S; vector subtree_size; vector set_index; vector ele_index; private: int get_subtree_size(int pos, int par){ int sz = 1; for(int ch : G[pos]){ if(ch == par) continue; sz += get_subtree_size(ch, pos); } return subtree_size[pos] = sz; } void make_path(int pos, int par, int set_id){ set_index[pos] = set_id; ele_index[pos] = S[set_id].element.size()-1; int largest_child = -1; int value = 0; for(int ch : G[pos]){ if(ch == par) continue; if(value < subtree_size[ch]){ value = subtree_size[ch]; largest_child = ch; } } for(int ch : G[pos]){ if(ch == par) continue; if(largest_child == ch){ S[set_id].element.push_back(ch); make_path(ch, pos, set_id); }else{ S.emplace_back( ch, S[set_id].depth+1, pos ); make_path(ch, pos, S.size()-1); } } } void init(){ subtree_size.resize(G.size(), 0); get_subtree_size(0,0); set_index.resize(G.size(), 0); ele_index.resize(G.size(), 0); S.emplace_back( 0,0,0 ); make_path( 0, 0, 0 ); subtree_size.clear(); } public: HeavyLightDecomposition(vector>& G_) : G(G_){ init(); } //set_index, element_index //S[set_index].element[element_index] == v pair get_position(int v){ return {set_index[v], ele_index[v]}; } }; int LCA(HeavyLightDecomposition& T, int u, int v){ auto pu = T.get_position(u); auto pv = T.get_position(v); if(pu.first == pv.first){ return pu.second < pv.second ? u : v; } if(T.S[pu.first].depth > T.S[pv.first].depth){ swap(pu, pv); swap(u,v); } while(T.S[pu.first].depth != T.S[pv.first].depth){ v = T.S[pv.first].parent_vertex; pv = T.get_position( v ); } while(pu.first != pv.first){ u = T.S[pu.first].parent_vertex; v = T.S[pv.first].parent_vertex; pu = T.get_position(u); pv = T.get_position(v); if(T.S[pv.first].depth == 0) break; if(T.S[pv.first].depth == 0) break; } if(pu.first == pv.first){ return pu.second < pv.second ? u : v; }else{ abort(); } return -1; } inline bool is_kadomatsu(int a, int b, int c){ return a!=c && ((ac) || (a>b&&b> n; vector a(n); fin >> a; vector> G(n); for(int i=0; i> u,v; u--; v--; G[u].push_back(v); G[v].push_back(u); } HeavyLightDecomposition T(G); vector> par(n, vector(20)); vector> kad(n, vector(20)); vector dep(n, -1); function dfs = [&](int pos, int last){ dep[pos] = dep[last]+1; par[pos][0] = last; if(is_kadomatsu(a[pos], a[last], a[par[last][0]])){ kad[pos][0] = 1; }else{ kad[pos][0] = 0; } for(int next : G[pos]){ if(next == last) continue; dfs(next, pos); } }; mt19937 mt(chrono::duration_cast(chrono::steady_clock::now().time_since_epoch()).count()); int root = uniform_int_distribution(0, n-1)(mt); dfs(root,root); for(int k=1; k<20; k++){ for(int i=0; i>= 1; } return pos; }; auto kadomatsu_line = [&](int u, int p) -> bool{ int d = dep[u] - dep[p] - 2; if(d<0) return true; d++; int ret = kad[u][0]; int b = 0; while(d>0){ if(d&1){ ret &= kad[u][b]; u = par[u][b]; } b++; d>>=1; } return ret; }; int q; fin >> q; while(q--){ int u,v; fin >> u,v; u--; v--; if(dep[u] < dep[v]) swap(u,v); int p = LCA(T, u,v); if(p==v){ int pu = k_anc(u, dep[u]-dep[p]-1); int qu = par[u][0]; bool ok = ( is_kadomatsu(a[pu],a[p],a[u]) && is_kadomatsu(a[p],a[u],a[qu]) && kadomatsu_line(u, p) ); fout << (ok?"YES":"NO") << fendl; }else{ int pu = k_anc(u, dep[u]-dep[p]-1); int pv = k_anc(v, dep[v]-dep[p]-1); int qu = par[u][0]; int qv = par[v][0]; bool ok = ( is_kadomatsu(a[pu], a[p], a[pv]) && is_kadomatsu(a[qu], a[u], a[v]) && is_kadomatsu(a[u], a[v], a[qv]) && kadomatsu_line(u,p) && kadomatsu_line(v,p) ); fout << (ok?"YES":"NO") << fendl; } } return 0; }