All Tracks Algorithms Graphs Minimum Cost Maximum Flow Problem

Isomorphic Trees
Tag(s):

Algorithms, Graphs, Medium-Hard, Minimum Cost Maximum Flow

Problem
Editorial
Analytics

You are given two trees. You are allowed to perform an operation several times: attaching a new vertex connect to an existing vertex of a tree. For each vertex A of the first tree and vertex B of second tree, we root the first tree at A and the second tree at B then your task is to find the minimum number of operations needed to make two trees isomorphic.

(Two rooted trees are isomorphic if they are the same size \(N\), and there is a permutation \(P\) of \(\{1, 2, \dots, N\}\) such that P["root of the first tree"] = "root of the second tree" and there is an edge between \(u, v\) in the first tree iff there is an edge between \(P[u], P[v]\) in the second tree.)

Input Format

The first line contains two space-separated integers \(N, M\) denoting the number of vertices of two trees.

Each of \(N - 1\) next lines contains two space-separated integers \(u, v\) denoting an edge \((u, v)\) of the first tree.

Each of \(M - 1\) next lines contains two space-separated integers \(u, v\) denoting an edge \((u, v)\) of the second tree.

Output Format

Output \(N\) lines, each line contains \(M\) space-separated integers. \(j\)-th number in the \(i\)-th line contains the answer if we root the first tree at vertex \(i\) and the second tree at vertex \(j\).

Constraints

  • \(1 \le N, M \le 50\).

 

SAMPLE INPUT
3 4
1 2
1 3
1 2
1 3
1 4
SAMPLE OUTPUT
1 3 3 3
3 1 1 1
3 1 1 1
Explanation

First tree:

Second tree:

  • If we root the first tree at vertex \(1\) and the second tree at vertex \(1\), then we must attach a new vertex to vertex \(1\) in the first tree to make two trees isomorphic. The cost is \(1\).
  • If we root the first tree at vertex \(1\) and the second tree at vertex \(2\), then we must attach two new vertcies to vertex \(2\) or \(3\) in the first tree and attach a new vertex to vertex \(2\) in the second tree to make two trees isomorphic. The cost is \(3\).
Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?