Hackwithinfyi | Infosys | OA Coding Questions and Solutions | Set - 4 | 2022

Question

Given a tree of 'N' nodes , undirected , answer 'M' queries on the tree.

Root is node - '1'.

1<=N<=100000

1<=M<=100000

EDGES = N - 1 .

Each node is assigned a character('a'-'z')

In each query , we are given an integer 'x' , we have to find all good nodes starting from node 'x' to/till root , such that the path starting from 'x' to node 'v'(v is the good node) , is a palindromic path.

 

A palindromic path in a tree is a path whose letters can be re arranged to form a palindrome.

Answer 1

Solution involed dynamic programming + bit-masking + manipulation of DFS.

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;
ll r = 0 ; 
vector <ll> G[200000];
ll used[200000];
ll value[200000];
unordered_map<ll,ll> a1;
ll number = 0 ; 
ll d[200000];
void DFS(ll node)
{
    //cout<<node<<endl ;
    ll koi = value[node] ; 
    ll t = 1 << koi ;
    number = (number)^(t);
    //cout<<node<<" "<<number<<endl;
    
    
    d[node] = d[node] + a1[number] ; 
    
    ll i = 0 ; 
    while(i<=25)
    {
        ll q = 1<<i ; 
        ll on = (number)^(q);
        d[node] = d[node] + a1[on] ; 
        i++;
    }
    
    
    
    a1[number]++;
    used[node] = 1 ; 
    for(auto u : G[node])
    {
        if(used[u]==0)
        {
            DFS(u);
        }
    }
    //cout<<node<<endl;
    ll koi1 = value[node] ; 
    ll t1 = 1 << koi1 ;
    number = (number)^(t1);
    a1[number]--;
    //cout<<node<<" "<<number<<endl;
}

int main() {
    a1[0] = 1 ; 
    ll n ; 
    cin>>n ; 
    ll i = 1 ; 
    while(i<=n-1)
    {
        ll x,y ; 
        cin>>x>>y ; 
        G[x].push_back(y);
        G[y].push_back(x);
        i++;
    }
    i = 1 ; 
    while(i<=n)
    {
        char x ; 
        cin>>x ; 
        ll po = int(x) - 97 ;
        value[i] = po ; //cout<<po<<endl;
        i++;
    }
    DFS(1);
    //cout<<r;
    int queries; 
    cin>>queries ; 
    i = 1 ; 
    while(i<=queries)
    {
        int x ; cin>>x;
        cout<<d[x]<<endl;
        i++;
    }
    
    return 0 ; 
}