PROBLEM LINK:
Author: Bhashkarjya Nath
Tester: Tushar Sain
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
PROBLEM:
The video game “Among Us” developed by InnerSloth is reaching new heights of popularity. In the recent update of the game, the InnerSloth developers added a new task for the players. This task was added to judge the level of the intelligence among the players.
The InnerSloth developers have designed a new map with rooms in it and paths connecting the rooms. The map has an added feature that each room belongs to at most one simple cycle.
A simple cycle in an undirected graph is a cycle with no repeated vertices (other than the requisite repetition of the first and last vertices).
The map has n rooms and m paths connecting the rooms. The crewmates have q number of tasks at hand. For each task, they will be given two room numbers, ai and bi. The imposters will make a journey from ai to bi, such that on the journey they don’t visit any room more than once. The crewmates have to answer the number of ways the imposters can make the journey. Since the value may be very large, you have to calculate the answer modulo 10^9+7.
#P.S.-
In the problem Among Us Update (CGAU05):- The output for the sample test case is not 2 2 it should be 1 1.
EXPLANATION:
The problem basically asks you to find the number of simple paths between some pair of vertices in the given graph. We can transform the graph into a tree by squeezing each cycle in one vertex. After the transformation, we will mark the vertices as 1-vertices if it is a squeezed cycle or as 0-vertices if it is a single vertex in source graph.
To find the number of paths between vertices a and b in source graph we will follow these steps. Let c is the representative vertex corresponding to a in the transformed tree and d is the representative vertex corresponding to b in the transformed tree. Let’s denote num is the number of 1-vertices in path from c to d in tree. We can observe that for every cycle that the imposter would encounter on the way from c to d, the number of paths would multiply by 2. So, the answer would be pow(2,num).
So, the task boils down to counting the number of 1-vertex on the path from one vertex to other in the tree in every query. We can do it in a following way. Call any vertex of the tree as a root.Suppose we want to find the number of 1-vertex on the path from A to B. Let C is the least common ancestor of vertices A and B.
Let us assume that-
x=number of 1 vertex on the way from A to the root(including root and A itself)
y=number of 1 vertex on the way from B to the root(including root and A itself)
z=number of 1 vertex on the way from C to the root(including root and A itself)
So, num=x+y-2z( if C is 0-vertex) or num=x+y-2z+1(if C is 1-vertex)
The least common ancestor can be found by using the technique of binary lifting.
SOLUTIONS:
Setter's Solution
(naIHsx - Online C++0x Compiler & Debugging Tool - Ideone.com)