TreeDistanceConstruction
SRM 704 · 2016-12-04 · by cgy4ever
SRM 704 · 2016-12-04 · by cgy4ever · Graph Theory
Problem Statement
Problem Statement
In a tree, the distance d(u,v) between vertices u and v is the smallest number of edges you need to traverse in order to get from u to v.
The eccentricity of a vertex u is the maximum of all d(u,v). In other words, the eccentricity of u is the distance between u and the vertex that is the farthest away from u.
You are given aint[] d with n elements.
Construct any tree with the following properties:
int[] .
If there are multiple such trees, you may output any of them.
If your tree contains the edges a[0] - b[0], a[1] - b[1], ..., a[n-2] - b[n-2], return the following int[] :
{a[0], b[0], a[1], b[1], ..., a[n-2], b[n-2]}.
Note that the return value should contain exactly 2*(n-1) elements.
The eccentricity of a vertex u is the maximum of all d(u,v). In other words, the eccentricity of u is the distance between u and the vertex that is the farthest away from u.
You are given a
- The tree has n vertices, numbered 0 through n-1.
- For each i, the eccentricity of vertex i is exactly d[i].
Constraints
- d will contain between 2 and 50 elements, inclusive.
- Each element in d will be between 1 and |d|-1, inclusive.
Examples
0)
{3,2,2,3}
Returns: {1, 2, 1, 0, 2, 3 }
The return value shown in this example describes the chain 0 - 1 - 2 - 3. This is one of multiple correct trees for this test case.
1)
{1,2,2,2}
Returns: {0, 1, 0, 2, 0, 3 }
In this case the only correct tree is a star with vertex 0 in the middle.
2)
{1,1,1,1}
Returns: { }
3)
{1,1,1}
Returns: { }
4)
{1,1}
Returns: {0, 1 }
Submissions are judged against all 154 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TreeDistanceConstruction with a public method vector<int> construct(vector<int> d) · 154 test cases · 2 s / 256 MB per case