0 like 0 dislike
2,502 views
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.

retagged | 2,502 views 0 like 0 dislike

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;
ll used;
ll value;
unordered_map<ll,ll> a1;
ll number = 0 ;
ll d;
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 = 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 ;
}```

by Expert (119,150 points)