A tree T consisting of n nodes An integer x Each node has some value w[i] associated with it. Task Determine the number of simple paths in the tree, such that the bitwise xor of elements on the simple path is x. Note: A simple path between node u and v is defined as a sequence of edges that connects node u and v and includes the occurrence of a node at most once. Example Assumptions n = 3 w = [3,2,2] edges = [(1,2), (1,3)] x = 1 Approach There exist two simple paths such that bitwise xor of elements on the path is x Two paths are from node 1 to node 2, 3 ^ 2 = 1 and node 1 to node 3, 3 ^ 2 = 1, where ^ is Bitwise Xor operator. Therefore, print 2. Complete the xor_paths function provided in the editor. This function takes the following 4 parameters and returns the answer: n: Represents the number of nodes in the tree w: Represents the value associated with each node x: Represents bitwise xor of elements on the simple path edges: Represents a 2D array containing n-1 edges representing edges in the tree. Input format Note: This is the input format that you must use to provide custom input (available above the Compile and Test button). The first line contains an integer t denoting the number of test cases. t also specifies the number of times you have to run the xor_paths function on a different set of inputs For each test case: The first line contains a single integer n denoting the number of nodes. The second line contains n space-separated integers representing array w. The third line contains a single integer x. n-1 lines follow, each containing two space-separated integers representing an edge between node u and v. Output format For each test case, print the answer in a new line. Constraints 1≤t≤101≤n≤1051≤u,v≤nu !=v0≤w[i],x≤15
Answers
Answer:
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
map<ll,ll>mp[30][30];
int n,m,t;
ll k,num[30][30],ans;
void dfs1(int x,int y,ll tt)
{
if(x+y==t)
{
mp[x][y][tt]++;
return ;
}
if(x+1<=n)
dfs1(x+1,y,tt^num[x+1][y]);
if(y+1<=m)
dfs1(x,y+1,tt^num[x][y+1]);
}
void dfs2(int x,int y,ll tt)
{
if(x+y==t+1)
{
if(x-1>=1)
ans+=mp[x-1][y][tt^k];
if(y-1>=1)
ans+=mp[x][y-1][tt^k];
return ;
}
if(x-1>=1)
dfs2(x-1,y,tt^num[x-1][y]);
if(y-1>=1)
dfs2(x,y-1,tt^num[x][y-1]);
}
int main()
{
while(~scanf("%d%d%lld",&n,&m,&k))
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
mp[i][j].clear();
scanf("%lld",&num[i][j]);
}
}
ans=0;
t=max(n,m);
if(1+1<=t)
{
dfs1(1,1,num[1][1]);
dfs2(n,m,num[n][m]);
}
else
{
if(num[1][1]==k)
ans++;
}
printf("%lld\n",ans);
}
}
Explanation:
It's working @kirankumar koneti