# NPL1701E - Editorial

Practice

Contest

Author: nmalviya1929
Editorialist: nmalviya1929

EASY MEDIUM

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:

1. if w is 0 or u and v are disconnected, then player 1 is definitely going to lose.

2. 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.

3. 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.

### RELATED PROBLEMS:

1 Like

Is the graph connected?

1 Like