PROBLEM LINK:
Author: nmalviya1929
Editorialist: nmalviya1929
DIFFICULTY:
EASY MEDIUM
PREREQUISITES:
Bipartite Graph
PROBLEM:
Given a graph with no odd cycles. Basically, graph is bipartite as there are no odd cycles. For every query of form u v w ,2 players play Nim game on a randomly selected path between u and v with all the edge weight as w. Find what is probability of first player winning the game.
QUICK EXPLANATION:
As graph is bipartite , if u and v are on same side , their xor will be zero and hence second player will win.And when u and v are on different side, first player will win for positive w.
EXPLANATION:
All the path from a vertex to itself are of even length. Hence graph have only even cycles. Such graph can be represented in bipartite form. For each query u v w possible answers are:
-
if w is 0 or u and v are disconnected, then player 1 is definitely going to lose.
-
if u and v lies on same part of bipartite graph , then all the path between them will be of even length . Hence their xor will be zero (Nim game) , and player 2 will win.
-
If u and v are on opposite side then all the path will be of odd length and there xor will be equal to w. For a positive value of w and connected u and v , player 1 will win.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.