SPOJ.com - Problem ADAORANG

ADAORANG - Ada and Orange Tree

#dfs #lowest-common-ancestor

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 test-cases.

The first line of each test case contains three integers 1 ≤ N, Q ≤ 4.5*10⁵, 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 N-1 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 test-cases won't exceed 10⁶

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

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

Submit solution!

hide comments

< Previous 1 2 Next >

	subhram79788: 2022-09-10 21:12:48 :/ my implementation: for each query, 1. find LCA 2. in the Euler tour tree(ETT), found the start and end indices of the LCA and in that I have tried to count the number of distinct shades by MO's algorithm(by sorting the query) verdict: 1. 2st TC is passing 2. but getting WA soln: <snip> [Simes]: use the forum for this. Last edit: 2022-09-10 23:09:38
	Shikhor Roy: 2022-07-13 09:15:16 @slimshadynick have you found any solution?
	Rafail Loizou: 2020-09-10 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? Also how is it possible writing an independent comment in the code make the difference between WA and TLE? [NG]: There is instability of servers that causes variance of runtime of the same solution and possibly yours just barely hits the TL on one of the testfiles sometimes, and TLEs otherwise. I've noticed you've been getting poor times in some of your other submissions that you never bother to improve on after AC so it's likely your code is hampered by bad style and resource management. Also make sure your I/O is up to the task as Morass' problems always come with huge testfiles. [Answer] : Why does it matter whether I improve my ACs or not? Once I get the AC I move to other problems. Also have you seen my code and you talk about my coding style being bad? I have made all the available optimizations (i.e reduced the function calls as much as possible, utilized stack memory as much as possible since it is faster than heap memory etc.) my I/O in C++ is fast (I'm using these two infamous commands "ios::sync_with_stdio(false);" and "cin.tie(0);" ). I will revisit this problem in the future though. Last edit: 2020-09-10 12:16:56
	sarthak_eddy: 2020-06-24 21:22:59 Nice problem with bitset and LCA easy implementation.
	vaibhav_717: 2020-06-02 17:30:23 simple LCA problem but very nice to solve
	slimshadynick: 2020-03-14 07:55:48 I am getting NZEC in test case 15 in java :/ , help please?
	sahil1422: 2019-12-18 18:59:31 Use bitset for easier implementation.
	surajk543: 2019-11-02 11:00:20 without fenwick Tree 9.93 sec and with fenwick tree 7 sec Last edit: 2019-11-02 11:03:17
	rniranjan93: 2019-08-21 15:30:53 i didn't get the question
	bibin: 2018-08-22 23:55:06 I have a O( N*log(N) ) solution and still got TLE

Submit solution!

Added by:	Morass
Date:	2017-02-10
Time limit:	2.5s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64