Weird Paths in a tree
You are given a tree. Each node of the tree is assigned a distinct value.
A path in the tree is considered weird if the values in the path increase and decrease alternatively.
For example: Consider a straight chain of nodes 1→3→2→4→5 with value assigned to any node i being i itself. Then the path 3→2→4, 1→3→2, etc. are weird whereas 1→3→2→4→5 is not weird because 2→4 and 4→5 are both increasing.
You are given Q queries. Each query contains the root of the tree, R, and an arbitrary node, S. For each query, you need to find the sum of all weird paths in the subtree rooted at S with respect to R being the root of the original tree. Sum of a path is defined as the sum of values assigned to all nodes on that path. As this sum could be very large, output it modulo M.Note:
- Paths of length 2 are always considered weird.
- A path is always defined for more than 1 node.
The first line of input contains 2 integers, N and M.
Second line contains N space separated numbers where the ith number denotes the value of the ith node. These N numbers are permutation of the sequence of numbers from 1 to N.
For the next N-1 line, each line contains 2 numbers a and b, denoting that node a is connected to node b.
Next line contains a single integer Q, the number of queries to follow.
Lastly, Q lines follow, where each line contains two space separated integers, R and S.
For each query, output the sum modulo M.
- 1 ≤ N ≤ 105
- 1 ≤ M ≤ 105
- 1 ≤ R ≤ N
- 1 ≤ S ≤ N
- 1 ≤ Q ≤ 105
Input: 6 100000 1 2 3 4 5 6 1 2 2 5 1 4 3 4 1 6 5 3 1 5 2 1 6 2 4 5 1 Output: 26 81 0 7 52
Query 1: Nodes in the subtree 1 are [1,2,5,6]. Valid Paths are 5→2 , 2→1, 1→6, 2→1→6 . Corresponding sums are 7, 3, 7, and 9. Total sum is 26.Note:
- A Path lies in a subtree if all nodes on the path are in the subtree.
|Tags||acmkol15, devuy11, dynamic-programming, medium-hard, rooted-trees, treeroot|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions