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.
Input
The first line of input contains 2 integers, N and M.
Second line contains N space separated numbers where the i^{th} number denotes the value of the i^{th} node. These N numbers are permutation of the sequence of numbers from 1 to N.
For the next N1 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.
Output
For each query, output the sum modulo M.
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ M ≤ 10^{5}
 1 ≤ R ≤ N
 1 ≤ S ≤ N
 1 ≤ Q ≤ 10^{5}
Example
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
Explanation
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.
Author:  devuy11 
Editorial  http://discuss.codechef.com/problems/KOL15E 
Tags  acmkol15, devuy11, dynamicprogramming, mediumhard, rootedtrees, treeroot 
Date Added:  14102015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions