BFS before DFS solution codechef

BFS before DFS solution codechef

Alice and Bob live in a country in which there are N cities (numbered from 1 to N) connected to each other using N-1 bidirectional roads in such a way that any two cities are reachable from each other.

This country has a special property: for each city in the country, there are at most 6 roads directly connected to it.

Alice and Bob both decide to go on a tour of the country, starting from city number 1. Alice uses Depth First traversal (DFS) order to travel through all the N cities while Bob uses Breadth First Traversal (BFS) order. At any city, if there is more than one possibility for the next city to be visited, then each option is equally likely to be chosen by both Alice and Bob.

The pseudocode of their respective traversals are as follows:

// Alice's DFS traversal
dfs(u):
    // Let C denote the set of children of u
    shuffle(C)
    // Let the current state of C be [C[1], C[2], ..., C[k]]
    for i from 1 to k:
        dfs(C[i])
// Bob's BFS traversal
queue Q
Q.push(1)
while Q is not empty:
    u = front(Q)
    pop(Q)
    // Let C denote the set of children of u
    shuffle(C)
    // Let the current state of C be [C[1], C[2], ..., C[k]]
    for i from 1 to k:
        Q.push(C[i])

Define the index of a city in some traversal order to be the number of distinct cities visited before that city during that traversal. Find the expected number of cities whose index in Bob’s traversal is strictly less than its index in Alice’s traversal.

It can be shown that this expected value can be expressed as a fraction \frac{P}{Q}, where P and Q are coprime integers, P \ge 0Q \gt 0 and Q is coprime with 998244353. You should compute (P \cdot Q^{-1}) \pmod {998\,244\,353}, where Q^{-1} denotes the multiplicative inverse of Q modulo 998\,244\,353.

BFS before DFS solution codechef

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • Each test case consists of multiple lines of input.
    • The first line of each test case contains a single integers N — the number of cities.
    • The next N-1 lines describe the roads. The i-th of these N-1 lines contains two space-separated integers u_i and v_i, denoting a road between cities u_i and v_i.

Output Format

For each test case, output on a new line (P \cdot Q^{-1}) \pmod {998\,244\,353}.

Constraints

  • 1 \leq T \leq 50
  • 1 \leq N \leq 200
  • 1 \leq u_i, v_i \leq N
  • Each city has at most 6 roads directly connected to it.
  • The sum of N over all test cases won’t exceed 300.

BFS before DFS solution codechef

Sample 1:

Input

Output

2
4
1 2
1 4
2 3
5
1 2
1 3
1 4
3 5
249561089
332748119

Explanation:

BFS before DFS solution codechef

Test case 1: There are two possible DFS traversals : [1,2,3,4] and [1,4,2,3]. Also, there are two possible BFS traversals : [1,2,4,3] and [1,4,2,3].

  • Probability that Bob reaches city 1 before Alice = 0
  • Probability that Bob reaches city 2 before Alice = \frac{1}{4}
  • Probability that Bob reaches city 3 before Alice = 0
  • Probability that Bob reaches city 4 before Alice = \frac{1}{2}

Therefore, the required expected value is \frac{1}{4}+\frac{1}{2} = \frac{3}{4}, which is 249561089 \pmod {998\,244\,353}

Leave a Comment