WalkOverATreeDiv2
SRM 666 · 2015-06-30 · by praveen123
Problem Statement
Surya has a tree with n nodes, numbered 1 through n. Each node contains some arbitrary nonnegative number of tokens.
Surya sometimes goes for a walk on the tree. He has to start his walk in node 1, but he may terminate it in any node of the tree. Surya gets tired easily: during the walk he is only able to traverse at most L edges.
Surya now wants to collect as many tokens as possible during a single walk. He can collect tokens in all nodes he visits, including the nodes where he starts and ends his walk. Obviously, the tokens in each node can only be collected once.
You are given the structure of the tree in
Return the maximum number of tokens Surya can collect.
Constraints
- n will be between 1 and 50, inclusive.
- A and B will contain exactly n-1 elements each.
- Each element of A and B will be between 1 and n, inclusive.
- A and B will define a tree.
- tokens will contain exactly n elements.
- Each element of tokens will be between 1 and 100, inclusive.
- L will be between 1 and 100, inclusive.
{1}
{2}
{7,1}
6
Returns: 8
This tree consists of two nodes and a single edge. There are 7 tokens in node 1 and 1 token in node 2. Surya can make at most six steps, which is more than enough to collect all 7+1 = 8 tokens.
{3,1}
{2,2}
{2,3,9}
5
Returns: 14
{1,2,5,3}
{4,4,1,4}
{6,1,6,4,4}
3
Returns: 16
This is a tree with five nodes. One optimal walk for this tree is to start in node 1, go to node 4, then to node 3, and then back to node 4. As L=3, this is the longest walk Surya may make. During this walk he will collect 6 tokens in node 1, 4 tokens in node 4, 6 tokens in node 3, and then 0 tokens when revisiting node 4. The total is 6+4+6+0 = 16 tokens. Another optimal walk is to start in node 1, go to node 4, then to node 3, and to stop there. Surya is not required to make all L steps.
{9,1,7,10,5,8,3,4,2}
{6,6,9,6,6,1,1,6,6}
{4,2,1,6,3,7,8,5,2,9}
4
Returns: 26
{25,22,35,42,40,9,32,12,37,44,23,1,24,28,20,4,26,33,11,48,34,6,16,50,46,17,8,43,18,30,31,36,39,13,
10,45,3,47,15,2,29,19,7,14,41,49,38,27,21}
{5,5,25,25,25,42,25,40,5,35,25,32,42,9,32,23,40,25,20,33,26,37,12,1,48,24,22,25,11,24,48,34,18,9,50,42,16,40,1,
10,47,22,48,44,48,1,4,46,47}
{6,9,4,9,5,8,6,4,4,1,4,8,3,4,5,8,5,6,4,9,7,9,7,9,5,2,7,2,7,7,5,9,5,8,5,7,1,9,3,9,3,6,4,5,5,4,7,9,2,2}
48
Returns: 194
Submissions are judged against all 97 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CollectingTokens with a public method int maxTokens(vector<int> A, vector<int> B, vector<int> tokens, int L) · 97 test cases · 2 s / 256 MB per case