LonglongestPathTree
SRM 635 · 2014-08-25 · by Xellos0
Problem Statement
There is a weighted tree with N vertices. The vertices are numbered 0 through N-1.
You're given a description of the tree in three
In a tree, each pair of vertices is connected by exactly one simple path.
The distance between those vertices is the sum of lengths of edges on that simple path.
The diameter of the tree is the maximum of all those pairwise distances.
You're allowed to remove one of the edges and then add another edge. There are two constraints: the length of this edge must be the same as the length of the removed edge and the resulting graph must again be a tree.
Compute and return the maximum diameter of the resulting tree that can be achieved this way.
Constraints
- N will be between 2 and 2,000, inclusive.
- Arrays A, B and L will each contain N-1 elements.
- Each element of A and B will be between 0 and N-1, inclusive.
- Each element of L will be between 1 and 1,000,000,000, inclusive.
- A and B will describe a tree.
{0,0,0}
{1,2,3}
{2,4,8}
Returns: 14
The tree has 4 vertices and 3 edges: 1-0 (length 2), 2-0 (length 4) and 0-3 (length 8). Currently, the farthest pair of vertices is (2,3); their distance is 8+4=12. If we remove the edge 1-0 and add an edge 3-1, we'll get a tree with edges 2-0 (length 4), 0-3 (length 8) and 3-1 (length 2). Now, the fathest pair of vertices is (2,1); their distance is 8+4+2=14. Obviously, we can't do better than that (but this is not the only way to achieve distance 14).
{0,1,2,3}
{1,2,3,4}
{1,2,3,4}
Returns: 10
One optimal solution is not changing the tree.
{0,1,0,3,0,6,7,7,8,9,11}
{1,2,3,4,5,5,5,8,9,10,9}
{100,1000,100,1000,1,10,10,10,10,100,100}
Returns: 2410
{1,5,6,4,4,0,3,3}
{6,6,4,8,0,3,2,7}
{1,1,1,1,1,1,1,1}
Returns: 7
{0,1,2,3,0,1,2,3,4}
{1,2,3,4,5,6,7,8,9}
{10,1,1,10,10,1000,100,1000,10}
Returns: 2122
{83,53,50,32,68,79,80,17,72,79,3,84,12,43,44,5,9,9,63,22,4,31,33,11,34,14,38,60,21,14,75,74,10,17,36,84,34,48,57,53,77,20,55,44,36,8,60,30,58,22,47,51,70,67,19,11,2,33,42,73,17,29,77,79,60,14,7,42,60,67,77,16,38,54,26,14,1,71,81,80,19,20,51,63}
{29,66,17,18,1,44,28,20,67,74,32,60,46,24,16,69,71,76,35,60,59,80,16,59,23,47,71,29,13,25,58,15,74,59,45,77,78,18,9,59,56,34,53,17,13,30,32,69,19,46,52,13,16,0,82,19,70,39,8,63,43,64,62,73,9,43,80,28,44,17,41,37,61,22,3,6,27,49,58,40,65,30,17,1}
{5509,8599,5012,9841,28943,3718,26975,32141,22407,14334,30106,24881,11481,27525,9155,21170,24988,14767,23347,4315,6908,20032,1708,20785,5879,5009,14897,7803,8397,9525,27418,130,10673,21979,28263,20758,22981,19574,12629,25169,11589,31900,24623,23072,29186,32300,28519,26366,14611,2100,15077,12803,4295,4882,12191,12830,6878,26073,13162,17567,21240,4854,16143,12024,6477,10259,24226,28100,21919,5435,3087,29960,18029,3903,6134,17849,20586,29017,5305,31871,25133,25104,30675,15801}
Returns: 478383
tests to contain (several times, each with near maxsize): - always weights: random, all near maximal, all 1, (sometimes) small random - random tree - random/balanced binary tree - random/balanced ternary tree - star - random 2-level star (tree of depth 3) - path; path with random leaves (few/many/together to form substars) - short path with big substars
Submissions are judged against all 89 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class LonglongestPathTree with a public method long long getLength(vector<int> A, vector<int> B, vector<int> L) · 89 test cases · 2 s / 256 MB per case