XOR DECOMPOSITION
Somebody help me how to get started with this kind of problems.
Chef has a tree with N nodes (numbered 1 through N) and a non-negative integer x. The nodes of the tree have non-negative integer weights; let's denote the weight of node i by ai.
Next, let's define the XOR value of a tree as the bitwise XOR of weights of all its nodes.
Chef wants to remove zero or more edges from his tree in such a way that each individual tree in the forest formed by removing these edges has XOR value x. Help him compute the number of ways to remove a set of edges such that this condition is satisfied. Since the answer may be large, compute it modulo 109+7.
Input
The first line of the input contains two space-separated integers N and x.
The second line contains N space-separated integers a1,a2,…,aN.
Each of the following N−1 lines contains two space-separated integers u and v denoting an edge between nodes u and v in Chef's tree.
Output
Print a single line containing one integer ― the number of ways to remove edges, modulo 109+7.
Constraints
1≤N≤105
0≤x≤109
0≤ai≤109 for each valid i
1≤u,v≤N
Example Input
7 1
1 0 1 0 1 0 1
1 2
1 3
2 4
2 5
3 6
3 7
Example Output
5
Explanation
There are five valid ways to remove edges, splitting the tree into subtrees on nodes:
[1, 2, 3, 4, 5, 6] and [7] by removing the edge (3-7)
[1, 2, 3, 4, 6, 7] and [5] by removing the edge (2-5)
[2, 4, 5] and [1, 3, 6, 7] by removing the edge (1-2)
[2, 4, 5], [1], [3,6] and [7] by removing edges (1-2), (1-3) and (3-7)
[1, 2, 4], [5], [3,6] and [7] by removing edges (2-5), (1-3) and (3-7)
Chef has a tree with N nodes (numbered 1 through N) and a non-negative integer x. The nodes of the tree have non-negative integer weights; let's denote the weight of node i by ai.
Next, let's define the XOR value of a tree as the bitwise XOR of weights of all its nodes.
Chef wants to remove zero or more edges from his tree in such a way that each individual tree in the forest formed by removing these edges has XOR value x. Help him compute the number of ways to remove a set of edges such that this condition is satisfied. Since the answer may be large, compute it modulo 109+7.
Input
The first line of the input contains two space-separated integers N and x.
The second line contains N space-separated integers a1,a2,…,aN.
Each of the following N−1 lines contains two space-separated integers u and v denoting an edge between nodes u and v in Chef's tree.
Output
Print a single line containing one integer ― the number of ways to remove edges, modulo 109+7.
Constraints
1≤N≤105
0≤x≤109
0≤ai≤109 for each valid i
1≤u,v≤N
Example Input
7 1
1 0 1 0 1 0 1
1 2
1 3
2 4
2 5
3 6
3 7
Example Output
5
Explanation
There are five valid ways to remove edges, splitting the tree into subtrees on nodes:
[1, 2, 3, 4, 5, 6] and [7] by removing the edge (3-7)
[1, 2, 3, 4, 6, 7] and [5] by removing the edge (2-5)
[2, 4, 5] and [1, 3, 6, 7] by removing the edge (1-2)
[2, 4, 5], [1], [3,6] and [7] by removing edges (1-2), (1-3) and (3-7)
[1, 2, 4], [5], [3,6] and [7] by removing edges (2-5), (1-3) and (3-7)
Last edited on
It's impossible to help you because you aren't trying to help us.
Do you know what a tree is?
Do you know what an edge is?
Do you know what a forest is?
Do you know what bitwise XOR is?
Have you worked out an example on paper?
What have you done?
What are your thoughts?
Do you have any thoughts?
Do you know what a tree is?
Do you know what an edge is?
Do you know what a forest is?
Do you know what bitwise XOR is?
Have you worked out an example on paper?
What have you done?
What are your thoughts?
Do you have any thoughts?
I am not getting any idea to proceed.
Just now I thought of finding those which doesn't have xor equal to x.
I don't know whether I am thinking in right direction.
Just now I thought of finding those which doesn't have xor equal to x.
I don't know whether I am thinking in right direction.
its is unlikely that brute force will succeed. You are looking for some pattern you can exploit. You may want to start with the properties of xor. start small and on paper. xor like 5 values together and see what the resulting value looks like.
@jonnin
Tnx for the help I will try it.
But I don't think there would be pattern.
Tnx for the help I will try it.
But I don't think there would be pattern.
Last edited on
but there are patterns to repeated xors. look at a single bit.
a bunch of ones xored is 0 if there are an even number of them, and 1 for an odd number:
1^1 = 0
1^1^1 = 1
1^1^1^1 = 0... etc
it may not help you. But as I said, there is something you need to find that avoids brute force.
a bunch of ones xored is 0 if there are an even number of them, and 1 for an odd number:
1^1 = 0
1^1^1 = 1
1^1^1^1 = 0... etc
it may not help you. But as I said, there is something you need to find that avoids brute force.
| Dumb wrote: |
|---|
| Yeah thinking but couldn't find anything at all. |
Then you either aren't thinking very well or this problem is beyond you.
Try something simpler.
Topic archived. No new replies allowed.