ADAORANG  Ada and Orange Tree
Ada the Ladybug lives near an orange tree. Instead of reading books, she investigates the oranges. The oranges on orange tree can be in up to 5*50 Shades of Orange. She walks from orange to orange, examining different properties of orange tree. The oranges are connected by branches. There is more oranges then branches, yet it is still possible to get from any orange to any other orange [through branches]. The tree is rooted.
Ada has many questions in following form: She goes from orange A to orange B (by shortest path) and is interested in total number different Shades of Orange among all subtrees of all edges on shortest path.
Input
The first line of input consists of 1 ≤ T ≤ 100, the number of testcases.
The first line of each test case contains three integers 1 ≤ N, Q ≤ 4.5*10^{5}, 0 ≤ R < N, the number of oranges, the number of questions and number of root.
Next line contains N integers 1 ≤ S_{i} ≤ 250, the shade of orange of orange i.
Next N1 lines contains two integers 0 ≤ I, J < N, I ≠ J , the numbers of oranges which are connected by branch.
Next Q lines contains two integers 0 ≤ A, B < N, the path Ada is interested about.
The sum of all N and all Q among all testcases won't exceed 10^{6}
Output
For each question answer the number of shades in all subtrees of all nodes on shortest path from A to B.
Example Input
1 10 7 1 1 2 1 4 5 6 6 8 9 9 0 9 9 3 3 4 4 6 4 5 4 8 1 3 1 2 2 7 4 4 8 6 0 6 7 0 7 2 0 0 2 3
Example Output
3 3 5 7 2 1 7
Explanation  shades in subtrees
5 6 9 5 6 9 1 4 5 6 9 1 2 4 5 6 8 9 1 8 1 1 2 4 5 6 8 9
hide comments
Rafail Loizou:
20200910 00:42:13
I'm literary done with this problem. Literary the same submission with just a comment difference and one gives TLE and the other gives WA. I did LCA with O(nlogn) construction and O(1) per query. Should I make this even faster?


sarthak_eddy:
20200624 21:22:59
Nice problem with bitset and LCA easy implementation. 

vaibhav_717:
20200602 17:30:23
simple LCA problem but very nice to solve 

slimshadynick:
20200314 07:55:48
I am getting NZEC in test case 15 in java :/ , help please? 

sahil1422:
20191218 18:59:31
Use bitset for easier implementation. 

surajk543:
20191102 11:00:20
without fenwick Tree 9.93 sec and with fenwick tree 7 sec Last edit: 20191102 11:03:17 

rniranjan93:
20190821 15:30:53
i didn't get the question 

bibin:
20180822 23:55:06
I have a O( N*log(N) ) solution and still got TLE 

markomafko972:
20180719 17:43:53
Try CLCKBAIT after this! 

soham_12345:
20180704 08:02:16
practise problem for sack though not a compulsion 
Added by:  Morass 
Date:  20170210 
Time limit:  2.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 