Dexter and Gangs

5

2 votes
Segment tree, Hard, Algorithms, Tree, Persistent Data Structures, Data Structures
Problem

Dexter lives with his girlfriend, Hannah. He plans to spend today's evening with her, driving his new car. The cities in his state are connected to each other via bi-directional roads in such a way that they form a tree.

As he has many enemies in the city, he needs to be careful in choosing the path for the road trip. In each city, resides a member of a certain gang, which wants to kill Dexter. Whenever Dexter passes through that city, the members of that gang become alert. Now, the good thing about these gangs for Dexter is that these gangs hate each other and don't go well with each other. So, a path is dangerous for dexter if and only if a gang exists on that path in majority. Otherwise the gang members end up fighting each other and the path becomes clear for dexter.

Definition of majority on a path : If the number of cities occupied by gang members of gang G on a path are x and the number of cities on that path are n, then gang G is in majority on that path if and only if x>n/2 .

There are N cities in the state and there are N1 bi-directional roads. Hannah comes up with M plans for the road trip. Each plan is of the form u,v, where road trip will take place from the city u to the city v along the unique path between them. For each plan, you need to tell whether the path in that plan is dangerous or not, and if it is dangerous, you need to output the number of the gang which is in majority on that path.

Input

First line of input contains two integers N and M, where N is the number of cities in the state and M is the number of plans suggested by Hannah. Next line contains N space separated integers Gi, where Gi is the number of the gang of the gang member in city i. Each of the next N1 lines contain two integers u and v, where u and v have a bi-directional road between them. Next M lines describe the query, i.e., the plan suggested by Hannah. Each of these lines contain two integers p and q, which represents the path between p and q.

Output

You need to output M lines. ith query is answered by ith line. If the path in the ith query is safe for Dexter, outpur "S" (withour quotes). If that path is dangerous and gang numbered x is in majority on that path, output "D x" (without quotes).

Constraints

1N105
1M106
1Gi 109
1u,vN
1p,qN

For 30% score : 1N,M103
For Full score : Original Constraints

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

enter image description here

The above figure shows the tree formed where each node number represents the city number. The numbers beside each node represent the gang number of the gang member present in that city.
Query 1 : The path from 4 to 6 is dangerous as gang number 3 is in majority, as it occurs 3 times on that path which is > 5/2.
Query 2 : There is no gang number in majority on the path from 2 to 3.
Query 3 : The path from 4 to 5 is dangerous as gang number 3 is in majority, as it occurs 2 times on that path which is > 3/2.

Editor Image

?