Link: https://www.nowcoder.com/questionTerminal/f58859adc39f4edc9cd8e40ba4160339 Source: NowCoder

The Magic Kingdom has a total of n cities, numbered from 0 to n-1. The roads between the n cities form exactly a tree. Xiaoyi is currently in city 0. Each move, Xiaoyi will walk from his current city to an adjacent city. Xiaoyi can move at most L times. If Xiaoyi has reached a city, he is considered to have toured that city. Xiaoyi now wants to make a good travel plan so that he can tour as many cities as possible. Please help him calculate the maximum number of cities he can tour (note that city 0 is already toured, and cities already toured are not counted again).

Input Description:

The input consists of two lines. The first line includes two positive integers n (2 ≤ n ≤ 50) and L (1 ≤ L ≤ 100), representing the number of cities and the number of moves Xiaoyi can make. The second line includes n-1 integers parent[i] (0 ≤ parent[i] ≤ i). For each valid i (0 ≤ i ≤ n - 2), there is a road connecting city (i+1) and city parent[i].

Output Description:

Output an integer representing the maximum number of cities Xiaoyi can tour.

Analysis

After abstracting the problem, it means traversing a tree, and after a specified number of steps, finding the path that passes through the maximum number of nodes. It might be easier to understand if we hang this tree from the root node. Although some solutions grow from bottom to top, I rebuilt the tree and used a hanging tree approach.

Starting from the root node, first determine whether the left subtree or the right subtree has a greater depth, and traverse the deeper subtree first. Continue until all steps are used up.

The depth of the tree can be easily calculated through post-order traversal, but it turns out this solution only passes 60% of the test cases.

45 73
0 0 0 1 0 0 3 5 6 8 7 9 1 10 1 2 15 6 8 11 14 17 8 14 3 21 23 3 21 15 12 5 21 31 11 13 7 17 20 26 28 16 36 26

The error is in this test case. The correct answer is 41, but using a simple greedy algorithm only yields 39 cities.

Later, looking at the explanation, I still couldn’t fully understand it. In any case, I saw that in the correct solution, the final answer is obtained directly after calculating the depth.

Suppose we have already calculated the maximum depth of each node, represented by deep[i], with the depth of the bottom layer of the tree being 1.

Obviously, the longest path from the root node to any node = deep[0] - 1.

Based on this path, we can visit some additional nodes. However, each time after visiting these nodes, we must return to this path. This round trip requires an extra two steps for each node visited, and visiting two nodes requires four extra steps.

Looking at the diagram makes it easier to understand:

Reference code:

#include <vector>
#include <iostream>
using namespace std;

vector<vector<int> > tree;
vector<int> deep;

void calc_deep(int i)
{
    int max_deep = 0;
    for(auto j:tree[i])
    {
        calc_deep(j);
        max_deep = max(deep[j], max_deep);
    }
    deep[i] = max_deep + 1;
}


int main()
{
    int n, L;
    cin >> n >> L;
    /* Build the tree */
    tree.resize(n);
    deep.resize(n);
    for(int i=0;i<n-1;i++)
    {
        int num;
        cin >> num;
        tree[num].push_back(i+1);
    }
    /* Calculate depth */
    calc_deep(0);
    // int validpath = min(deep[0] -1,L);
    // cout << min(n, 1 + validpath + (L - validpath)/2) << endl;
    int long_path = deep[0] - 1;
    if(long_path > L)  cout << L + 1;
    else cout << 1 + long_path + (L - long_path)/2;
    
}