#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //input from stdin template istream& operator >> (istream& is, vector& vec){for(T& val: vec) is >> val; return is;} template istream& operator , (istream& is, T& val){ return is >> val;} template ostream& operator << (ostream& os, const vector& vec){for(int i=0; i ostream& operator , (ostream& os, const T& val){ return os << " " << val;} template ostream& operator >> (ostream& os, const T& val){ return os << " " << val;} bool is_kadomatsu(vector v){ if(v.size()!=3) return false; if(v[0]==v[1] || v[1]==v[2] || v[2]==v[0]) return false; return (v[0]v[2]) || (v[0]>v[1] && v[1]> n; vector a(n); cin >> a; vector> G(n); for(int i=0; i> u,v; //scanf("%d%d", &u,&v); u--,v--; G[u].push_back(v); G[v].push_back(u); } vector depth(n, -1); vector kadomatsu(n, 0); vector> par(n, vector(20)); function dfs = [&](int pos, int last, int last2){ kadomatsu[pos] = is_kadomatsu({a[pos],a[last],a[last2]}); depth[pos] = depth[last]+1; par[pos][0] = last; for(int next : G[pos]){ if(next == last) continue; dfs(next, pos, last); } }; dfs(0,0,0); for(int k=1; k<20; k++){ for(int i=0; i>=1, i++) if(k&1) pos = par[pos][i]; return pos; }; auto lca = [&](int x, int y){ if(depth[x] < depth[y]) swap(x,y); x = kth_parent(x, depth[x] - depth[y]); if(x==y) return x; for(int k=19; k>=0; k--){ if(par[x][k] != par[y][k]){ x = par[x][k]; y = par[y][k]; } } return par[x][0]; }; vector log_k(n+1, 0); for(int i=2, tmp=0; i0; }; int q; cin >> q; while(q--){ int u,v; //scanf("%d%d", &u,&v); cin >> u,v; u--,v--; assert(u!=v); int p = lca(u,v); bool ok = true; if(p==u || p==v){ //straight line if(p==u) swap(u,v); // v==p int pu = kth_parent(u, depth[u]-depth[p]-1); int qu = par[u][0]; ok = is_kadomatsu_line(u,p) && is_kadomatsu({a[qu], a[u], a[p]}) && is_kadomatsu({a[u], a[v], a[pu]}); }else{ int pu = kth_parent(u, depth[u]-depth[p]-1); int pv = kth_parent(v, depth[v]-depth[p]-1); int qu = par[u][0]; int qv = par[v][0]; ok = ( is_kadomatsu_line(u,p) && is_kadomatsu_line(v,p) && is_kadomatsu({a[pu], a[p], a[pv]}) && is_kadomatsu({a[qu], a[u], a[v] }) && is_kadomatsu({a[u], a[v], a[qv]}) ); } if(ok) cout << "YES" << "\n"; else cout << "NO" << "\n"; } return 0; } int main(){ //auto s = clock(); main_(); //cerr << clock()-s << " [ms] " << endl; return 0; }