XYZ Path queries
Practice
4.7 (16 votes)
Algorithms
Bit manipulation
Combinatorics
Depth first search
Dynamic programming
Graphs
Lowest common ancestor
Trees
Problem
89% Success 3349 Attempts 50 Points 1.2s Time Limit 256MB Memory 1024 KB Max Code
Given a tree with N nodes (numbered 1 to N). For each valid i, the i-th node has a value of A[i] associated with it.
Your target is to handle the queries of the following 4 types -
- "1 X Y": Sum of values of all the nodes in the path from X to Y.
- "2 X Y": Sum of pairwise OR of every possible pair in the path from X to Y i.e. ∑(a[i] | a[j]) where i < j.
- "3 X Y": Sum of OR of all triplet in the path from X to Y i.e. ∑(a[i] | a[j] | a[k]) where i < j < k.
- "4 X Y": Sum of OR of all groups of type (a,b,c,d) in the path from X to Y i.e. ∑(a[i] | a[j] | a[k] | a[l]) where i < j < k < l.
For each query answer can be very large so print it MODULO 1000000007 (1e9 + 7).
Input -
- First-line contains N, the number of nodes in the tree
- Next line contains N space-separated integers denoting A[i]
- Next N-1 lines contain two space-separated integers x and y which denote that there is an edge between node u and node v.
- The next line contains Q, the number of queries to process.
- Next, Q lines follow with one of the four queries per line.
Output-
For each query print a single integer denoting it's sum as described in the problem.
Constraints -
- 1 <= N <= 100000 (1e5)
- 1 <= Q <= 100000 (1e5)
- 1 <= X,Y <= N
- 1 <= a[i] <= 1000000000 (1e9)
Explanation
- For 7th query i.e. 2 2 4
- Type = 2 so all pairs sum
- Path is from 2 to 4
- Path contains values of A[i] = 62,24,56,12
- All possible pairs = (62,24) (62,56) (62,12) (24,56) (24,12) (56,12)
- Sum = 62 + 62 + 62 + 56 + 28 + 60 = 330
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
22 votes
Tags:
GraphsMediumOpen
Points:50
23 votes
Tags:
Depth First SearchMediumTrees
Points:50
1 votes
Tags:
AlgorithmsDepth First SearchGraphsMedium
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Results
Custom Input
Run your code to see the output