TopCoder SRM 578 - 1000: DeerInZooDivOne

Problem Statement

给定一棵n个节点的树，要求找出两个最大的没有公共点的同构连通块。求这两个连通块的大小。
两个连通块A,B同构是指存在一组A的点编号集合到B的点编号集合的双射p，
使得如果A中的点u,v之间有一条边,那么B中的点p(u),p(v)之间也有一条边。
n <= 51.

Deer Only has recently shed his antlers. He is now ashamed and wants to make fake ones until the real ones grow back.

Deer Only has found a tree with N vertices. The vertices are numbered 0 through N-1. You are given two int[]s a and b that contain N-1 integers each. These arrays describe the edges of the tree: for each i, the vertices a[i] and b[i] are connected by an edge.

Deer Only has decided to make his new antlers out of this tree. The only operation he is able to do is to remove some edges from his tree, producing several smaller trees. Then, he wants to take two of the newly created trees and attach them to his head. The two antlers must be isomorphic, otherwise he will be unbalanced when running. (See Notes for a formal definition of tree isomorphism.)

Return the maximal size of the deer's new fake antlers. The size of an antler is defined as the number of vertices in it. Note that the largest possible antlers may sometimes consist only of a single vertex (and no edges).

Definition

Class DeerInZooDivOne
Method getmax
Parameters vector<int> , vector<int>
Returns int
Method signature int getmax(vector<int> a, vector<int> b)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Notes

Two trees T1 = (V1, E1) and T2 = (V2, E2) are called isomorphic if there exists a bijection f from V1 to V2 with the following property: For each pair of vertices in V1 (a, b), there is an edge between a and b in T1 if and only if there is an edge between f(a) and f(b) in T2.

Constraints

N will be between 2 and 51, inclusive.
a and b will contain exactly N-1 elements each.
Each element of a and b will be between 0 and N-1, inclusive.
The edges described by a and b will form a tree.

Test cases

input
- a { 0, 1, 2 }
- b { 1, 2, 3 }
output
Returns 2

note

The tree looks as follows: 0-1-2-3. Deer Only can remove the edge between the vertex 1 and the vertex 2, and he gets two new trees 0-1 and 2-3. These two trees are isomorphic, so he can use these two trees as antlers.
input
- a { 1, 8, 1, 7, 4, 2, 5, 2 }
- b { 5, 3, 6, 8, 2, 6, 8, 0 }
output
Returns 4

note

The two new trees will contain vertices 0,2,4,6 and 5,8,7,3.
input
- a { 0 }
- b { 1 }
output
Returns 1
input
- a { 0, 11, 10, 10, 19, 17, 6, 17, 19, 10, 10, 11, 9, 9, 14, 2, 13, 11, 6 }
- b { 7, 5, 2, 12, 8, 9, 16, 8, 4, 18, 8, 13, 15, 13, 17, 16, 3, 1, 7 }
output
Returns 8
input
- a { 14, 13, 28, 15, 20, 4, 9, 6, 1, 23, 19, 25, 25, 8, 14, 16, 2, 8, 15, 25, 22, 22, 28, 10, 10, 14, 24, 27, 8 }
- b { 21, 5, 12, 13, 27, 1, 24, 17, 27, 17, 23, 14, 18, 26, 7, 26, 11, 0, 25, 23, 3, 29, 22, 11, 22, 29, 15, 28, 29 }
output
Returns 11

back to the menu