BLTOUR - Editorial

general
, , , ,
1

Problem Link

Practice

Contest

Author: Ankur Verma

Tester: Raju Varshney

Editorialist: Vaibhav Tulsyan & Raju Varshney

Difficulty

Easy

Pre-requisites

Graphs, Depth First Search

Problem

Given a rooted tree, find the number of ways to traverse the tree, starting from the root.

Quick Explanation

The number of ways is the product of factorials of number of children of each node.

Explanation

First, it must be noticed that since every node is reachable from every other node and there are N - 1 edges, the graph is a tree.

Let some Parent node be P and its children be C_1, C_2, C_3, … , C_n, then:

ways(P) = n!

This is because, after P is visited, its children will be visited in some order - the number of ways to order the children would be factorial of the number of children of P.

Hence, by the counting principle, the total number of ways to traverse the tree would be =

children(1)! * children(2)! * … * children(N)!

where children(X) represents the number of children of node X in the rooted tree.

Related problems

  1. http://www.spoj.com/problems/PT07Y/
2 Likes
2

Here is my code :slight_smile:

https://www.codechef.com/viewsolution/9976871

3

Here is my DFS Code, After building the adjacency list, the answer would simply be dfs(root,-1);

dfs(pos,par){
    ret = max(1,adj[pos].size()-1+(pos==par));
    ret = factorial(ret);
    for(int child :adj[pos])
	    if(child!=par)
		    ret=(ret*dfs(child,pos))%mod;
    return ret;
}