SRM 565 1 1000 UnknownTree

Problem Statement

Definition

Limits

Notes

• The distance between two vertices s and t is defined as the sum of lengths of all edges on the only simple path between s and t.
• Two trees T1 and T2 are different when T1 has an edge u-v such that in T2 the edge u-v is either not present at all, or it has a different length than the edge u-v in T1.

Constraints

• distancesA, distancesB, and distancesC will contain the same number of elements.
• distancesA, distancesB, and distancesC will contain between 1 and 50 elements, inclusive.
• Each element of distancesA, distancesB, and distancesC will be between 1 and 100,000,000, inclusive.

Test cases

0. input

   • distancesA { 1 }
   • distancesB { 2 }
   • distancesC { 3 }

   output

   Returns 6

   note

   
1. input

   • distancesA { 1, 2 }
   • distancesB { 1, 2 }
   • distancesC { 1, 2 }

   output

   Returns 1

   note

   
2. input

   • distancesA { 5, 4 }
   • distancesB { 3, 2 }
   • distancesC { 2, 1 }

   output

   Returns 8
3. input

   • distancesA { 2, 4, 2 }
   • distancesB { 1, 3, 3 }
   • distancesC { 4, 6, 4 }

   output

   Returns 2
4. input

   • distancesA { 4, 6, 1, 5, 3, 2, 5 }
   • distancesB { 4, 2, 3, 1, 3, 2, 1 }
   • distancesC { 5, 7, 2, 6, 4, 3, 6 }

   output

   Returns 12
5. input

   • distancesA { 6, 4, 5, 6, 8, 1, 5, 6, 4, 2 }
   • distancesB { 4, 2, 3, 4, 6, 1, 3, 4, 2, 2 }
   • distancesC { 6, 4, 5, 6, 8, 3, 5, 6, 4, 4 }

   output

   Returns 9000
6. input

   • distancesA { 8, 5, 6, 8, 6, 5, 6, 10, 8, 5, 10, 8, 7, 9, 7, 1, 11, 5, 9, 6, 6, 1, 6, 9, 8, 4, 12, 7, 5, 7, 6, 8, 12, 8, 6, 6, 5, 8, 5, 3, 3, 4, 8, 6, 6, 8, 8, 9, 7, 5 }
   • distancesB { 9, 6, 7, 9, 7, 6, 7, 11, 9, 6, 11, 9, 8, 10, 8, 2, 12, 6, 10, 7, 7, 4, 7, 10, 9, 5, 13, 8, 6, 8, 7, 9, 13, 9, 7, 7, 6, 9, 6, 4, 4, 5, 9, 7, 7, 9, 9, 10, 8, 6 }
   • distancesC { 8, 9, 6, 8, 2, 5, 6, 10, 8, 5, 10, 8, 7, 9, 1, 5, 11, 5, 9, 6, 6, 7, 6, 9, 8, 4, 12, 7, 5, 7, 6, 8, 12, 8, 6, 6, 5, 8, 1, 7, 3, 4, 8, 6, 6, 8, 8, 3, 7, 5 }

   output

   Returns 770724166
7. input

   • distancesA { 33030780, 30296205, 16842859, 28857842, 37928939, 27190807, 48689043, 33328845, 24254103, 3962046, 31043603, 25699520, 11297547, 27045586, 31603483, 23207518, 44089781, 48470539, 52366295, 39786470, 45623279, 21593844, 38639305, 27260993, 43899542, 36162768, 21640232, 43580853, 33826577, 30501815, 51470990, 2157904, 27823597, 9550575, 39234641, 24163007, 34155133, 42504989, 35821444, 36054200, 29026389, 29716374, 41764139, 19392309, 44258194, 19987908, 56722905, 46771885, 32668277, 40665175 }
   • distancesB { 16191697, 13457122, 3776, 12018759, 21089856, 10351724, 31849960, 16489762, 7415020, 12877037, 14204520, 8860437, 9035480, 10206503, 14764400, 6368435, 27250698, 31631456, 35527212, 22947387, 28784196, 4754761, 21800222, 10421910, 27060459, 19323685, 4801149, 26741770, 16987494, 13662732, 34631907, 18996987, 10984514, 7288508, 22395558, 7323924, 17316050, 25665906, 18982361, 19215117, 12187306, 12877291, 24925056, 2553226, 27419111, 3148825, 39883822, 29932802, 15829194, 23826092 }
   • distancesC { 19337227, 16602652, 3149306, 15164289, 24235386, 13497254, 34995490, 19635292, 10560550, 16030119, 17350050, 12005967, 12188562, 13352033, 17909930, 3215353, 30396228, 34776986, 38672742, 26092917, 31929726, 7907843, 24945752, 13567440, 30205989, 22469215, 7946679, 29887300, 20133024, 16808262, 37777437, 22150069, 14130044, 10441590, 25541088, 10469454, 20461580, 28811436, 22127891, 22360647, 15332836, 16022821, 28070586, 5706308, 30564641, 6294355, 43029352, 33078332, 18974724, 26971622 }

   output

   Returns 101733071