#include #include #include #include #include #include #include using namespace std; bool kadomatsu(int x,int y, int z){ if( x==y || y==z || z==x ) return false; if( xz ) return true; if( x>y && y edge[100000]; int up(int cur, int d){ if( d==0 ) return cur; int ex=0; int ret = cur; while( (1<=0 ){ if( (d&(1<> val[i]; for( int i = 0 ; i st; st.push(0); depth[0]=0; parent[0][0]=-1; while( !st.empty() ){ int cur = st.top(); st.pop(); for( int ei=0; ei < (int)edge[cur].size(); ei++){ int nxt = edge[cur][ei]; if( depth[nxt]!=-1 ) continue; depth[nxt]=depth[cur]+1; parent[0][nxt]=cur; iskadsequence[0][nxt]=true; int tmpCur=cur; int tmpNxt=nxt; for( int i = 0;parent[i][tmpCur]!=-1;i++){ parent[i+1][nxt]=parent[i][tmpCur]; iskadsequence[i+1][nxt]=(iskadsequence[i][nxt]&iskadsequence[i][tmpCur]&kadomatsu(val[parent[0][tmpCur]],val[tmpCur],val[tmpNxt])); tmpCur=parent[i][tmpCur]; tmpNxt=parent[i][tmpNxt]; } st.push(nxt); } } /* for( int i = 0 ; i < N; i++ ){ cout << depth[i]<<", "; } cout << endl; for( int i = 0 ; i depth[v] ){ swap(u,v); } if( parent[0][u]==v || parent[0][v]== u){ printf("NO\n"); continue; } int v2=up(v,depth[v]-depth[u]); if( v2 == u ){ int child_v=up(v,depth[v]-depth[u]-1); if( checkKadSeq(v,depth[v]-depth[u]) && kadomatsu(val[parent[0][v]],val[v],val[u]) && kadomatsu(val[child_v],val[u],val[v])){ printf("YES\n"); } else{ printf("NO\n"); } continue; } int p=lca(u,v2); int child_u=up(u,depth[u]-depth[p]-1); int child_v=up(v,depth[v]-depth[p]-1); // cout << v2<<", "<