0w1

CFR 570 D. Tree Requests ( XOR, bits, DFS )

Problem - D - Codeforces
First, we will notice that iff there are more than 1 alphabet with frequency of an odd number, a palindrome sequence cannot be formed. Thus we are only concerned with whether the frequency of each alphabet is odd or not. And since there are at most 26 distinct characters, we can compress them in the form of bits in integer. XOR will take care of adding compressed informations about the parities. Then, we will perform DFS, storing the parity information of visited subtrees for each particular depth. Each time when we are at the node of some query that match as the root of their subtrees, we will perform XOR on the array that maps, then DFS further, at last XOR again. As you might have some clues already, with the DFS done exhaustively while only traversing nodes in the subtree of the current one, performing the 2 XORs in such order will provide us the pure parity information for the parity of the query.

void dfs( int u, int d, const string &s, const vvi &G, vi &dpt_trait, const vvp &Q, vi &ans ){
    for( pii p : Q[ u ] )
        ans[ p.second ] ^= dpt_trait[ p.first ];
    dpt_trait[ d ] ^= 1 << ( s[ u ] - 'a' );
    for( int v : G[ u ] )
        dfs( v, d + 1, s, G, dpt_trait, Q, ans );
    for( pii p : Q[ u ] )
        ans[ p.second ] ^= dpt_trait[ p.first ];
}

void solve(){
    int N, M; cin >> N >> M;
    vvi G( N );
    for( int i = 1; i < N; ++i ){
        int fa; cin >> fa;
        G[ fa - 1 ].push_back( i );
    }
    string s; cin >> s;
    vvp Q( N );
    for( int i = 0; i < M; ++i ){
        int v, h; cin >> v >> h;
        Q[ v - 1 ].push_back( pii( h, i ) );
    }
    vi ans( M );
    vi dpt_trait( N + 1 ); // trait by depth
    dfs( 0, 1, s, G, dpt_trait, Q, ans );
    for( int i = 0; i < M; ++i ){
        if( ( ans[ i ] ^ ( ans[ i ] & -ans[ i ] ) ) ) cout << "No\n";
        else cout << "Yes\n";
    }
}