Connection Status:
Competition Arena > TreesAnalysis

TreesAnalysis

SRM 621 · 2013-12-22 · by boba5551

SRM 621 · 2013-12-22 · by boba5551 · Dynamic Programming, Graph Theory
Class Name: TreesAnalysis
Return Type: long
Method Name: treeSimilarity
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

Vasa has two undirected trees. Each of the trees has n vertices. In each tree, the vertices are labeled 0 through n-1, inclusive, in no particular order. The shapes of the trees may be different.


You are given the description of the two trees as int[]s tree1 and tree2 with n-1 elements each. For each valid i, the vertices i and tree1[i] are connected by an edge in the first tree. Similarly, for each valid i, the vertices i and tree2[i] are connected by an edge in the second tree.


Vasa tried to measure how similar the two trees are. He did so in two steps. First, he defined the value S(e1,e2): the similarity between the edge e1 in the first tree and the edge e2 in the second tree. Then, he defined the similarity between his two trees as the sum of sqr(S(e1,e2)) over all pairs (e1,e2), where sqr(x)=x*x. The definition of S(e1,e2) follows.


We will now define the similarity S(e1,e2). Consider the following process:

  • If we were to remove the edge e1 from the first tree, it would split into two components. Choose one of them and call it A.
  • If we were to remove the edge e2 from the second tree, it would split into two components. Choose one of them and call it B.
  • Let X be the set of labels that are present both in A and in B.

Then, the similarity S(e1,e2) is defined to be the largest possible size of the set X. (The maximum is taken over both choices of A and both choices of B.)


Compute and return the similarity between the two given trees.

Notes

  • An undirected graph is a tree if and only if between any two vertices of the graph there is exactly one simple path (i.e., one that never visits the same node twice).

Constraints

  • n will be between 2 and 4,000, inclusive.
  • tree1 will contain n - 1 elements.
  • tree1 and tree2 will contain the same number of elements.
  • Each element of tree1 will be between 0 and n - 1, inclusive.
  • Each element of tree2 will be between 0 and n - 1, inclusive.
  • tree1 and tree2 will represent trees as described in the problem statement.
Examples
0)
{1}
{1}
Returns: 1

The similarity between the edge 0-1 in the first tree and the edge 0-1 in the second tree is 1. One corresponding set X is the set X = {0}.

1)
{2, 4, 1, 0}
{1, 4, 4, 4}
Returns: 111

Here the first tree is a path (edges 0-2, 1-4, 2-1, and 3-0) and the second tree is not a path (edges 0-1, 1-4, 2-4, and 3-4). As each tree has four edges, their similarity is the sum of 4*4 = 16 terms. For example, let's compute one of those 16 terms. The similarity between the edge e1 = 0-2 in the first tree and the edge e2 = 0-1 in the second tree is 3, as depicted in the figure below. Hence, this pair of edges contributes sqr(3) = 3*3 = 9 towards the total similarity between these two trees.

2)
{1, 2, 3, 4}
{1, 2, 3, 4}
Returns: 128
3)
{2, 3, 4, 4, 5, 8, 5, 6, 10, 8}
{9, 0, 1, 0, 3, 0, 5, 0, 7, 10}
Returns: 6306
4)
{1, 2, 3, 4, 5, 6, 7, 8, 9}
{9, 0, 1, 2, 3, 4, 5, 6, 7}
Returns: 2724

Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TreesAnalysis with a public method long long treeSimilarity(vector<int> tree1, vector<int> tree2) · 60 test cases · 2 s / 256 MB per case

Submitting as anonymous