游历魔法王国

• 若 L ≤ maxLen ，显而易见得结果；
• 若 L > maxLen ，意味着可以往回走，要知道越短的树链往回走的代价越低。如果从末端往回走，消耗的代价非常高，最坏情况是较短的树链都连接在最远的树根上，整条最长链都要回走；如果已经知道最终步数会有剩余，则可以先消耗富余的步数走短链，最后才走最长链；
• 继续对 rest = L - maxLen 进行讨论：
  • 若树链上存在某个节点拥有另一条子链，其长度 x 必定小于或等于该祖先到原链末端的长度，考察树链上每个节点到叶子的一条最短子链：
    • 当 x > rest/2 可以在中途预先用掉 rest 步而不影响要走的 maxLen 最长链，可达城市增加 rest/2 个；
    • 当 x ≤ rest/2 可以在中途预先用掉 2x 步而不影响要走的 maxLen 最长链，可达城市增加 x 个；
  • 若所有的 x 总和 sum(x) ≤ rest/2 说明富余的步数足够把最短链到次最长链都走一遍，可达城市为全部 n 个。
  • 本小节讨论可知 rest/2 决定了能多走的城市数量，总共能走 min(n, 1 + rest/2 + maxLen) 个城市。

#include <stdio.h>
#include <string.h>

#define MAXN 55
#define MAXM 55

inline void getMax(int& n, int x) {
    n < x && (n = x);
}

inline void getMin(int& n, int x) {
    n > x && (n = x);
}

struct Edge {
    int to;
    int next;
} edge[MAXM];

int cnt;
int head[MAXN], len[MAXN];

void init() {
    memset(head, 0xff, sizeof(head));
}

void addEdge(int u, int v) {
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

int n, L;

void read() {
    int parent;
    scanf("%d%d", &n, &L);
    for (int i = 1; i < n; ++i) {
        scanf("%d", &parent);
        addEdge(parent, i);
    }
}

void walk(int u) {
    for (int i = head[u]; ~i; i = edge[i].next) {
        len[edge[i].to] = len[u] + 1;
        walk(edge[i].to);
    }
}

void work() {
    walk(0);
    int maxLen = 0;
    for (int i = 0; i < n; ++i) {
        getMax(maxLen, len[i]);
    }
    if (L <= maxLen) {
        printf("%d\n", L + 1);
    } else {
        int res = n;
        getMin(res, maxLen + (L - maxLen) / 2 + 1);
        printf("%d\n", res);
    }
}

int main() {
    init();
    read();
    work();
    return 0;
}

没看见有java语言，我这里添加一个。 思路和一楼基本一致，我的代码建树的过程可以更优化一些。
测试用例：
10 10
0 3 1 3 0 5 2 7 5
建树后，运行完getstep(City city)、检索玩得到max方法后，图的形状和对应的步数。如下图。

代码：

import java.util.ArrayList;
import java.util.Scanner;
/**
 * 个人博客 [www.mynight.top](http://www.mynight.top) ，欢迎光顾
 * 魔法王国
 */
public class MagicCity {
    static int x = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int L = in.nextInt();
        City[] citys = new City[n];//从0开始到n均为城市
        for(int i=1;i<n;i++)//计数从1开始，自动+1
        {
            int tmp = in.nextInt();//i城市的上一个城市为tmp，tmp下属城市包含i
            if(citys[i]==null) citys[i] = new City();
            if(citys[tmp]==null) citys[tmp] = new City();
            citys[i].pre = citys[tmp];
            citys[tmp].list.add(citys[i]);
        }
            getstep(citys[0]);//将每个结点的step标记。
        int max = 0;//记录最常的那条链表
        for (int i=0;i<citys.length;i++)
        {
            if(citys[i].step>max)max = citys[i].step;
        }
        if(max>=L){//判断L是否能走到最常的链表处
            System.out.println(L+1);
            return;
        }
        //如果走完max长度后，还有剩余的步数。
        int rest = (L-max)/2;//最多还能走的步数（包括返回）
        //可以很容易的证明，剩下未走过的城市，每多游玩一个城市，就需要花费两步。
        int x = n-max-1;//剩下未走过的城市个数
        if(rest>=x)
            System.out.println(n);
        else{
            System.out.println(max+1+rest);
        }
    }
    private static void getstep(City city)
    {
        for (int i=0;i<city.list.size();i++)
        {
            city.list.get(i).step = city.step+1;
            getstep(city.list.get(i));
        }
    }
    static class City{
        int step;
        City pre;
        ArrayList list = new ArrayList();
    }
}

题目经过抽象之后，意思是在一个树中进行遍历，经过指定步数，可以获取最长经过节点树量的路径。如果把这个树按照根节点进行悬挂，可能更好理解一些。虽然有些答案是从低向上生长，但是我还是重建了树，采用悬挂树来做的。

从这个根节点开始遍历，先判断左树深度大还是右树深度大，先遍历树深度大的那个节点。直到步数用完为止。

树的深度通过后序遍历很容易求出来，结果发现这样的答案只能通过60%。

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

错在这个用例上了。这个正确答案是41，通过简单的贪心算法只能得到39个城市。

后来看了解析也是看不太懂。总之之后看到正确答案中是求出来深度后直接获得最终答案。

假设我们已经求出了每一个节点的最大深度，用deep[i]来表示，树的最下面一层的深度是1。

显然，根节点到任意一个节点的最长路径=deep[0]-1。

以这条路径为基础，我们可以额外访问一些节点。但是每次访问完这些节点的时候，我们必须回来这个路径。这一来一回，每次访问一个节点都必须额外走两步，访问两个节点就必须走4步。

看图就容易明白一些：

参考代码

#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;
    /* 建立树 */
    tree.resize(n);
    deep.resize(n);
    for(int i=0;i<n-1;i++)
    {
        int num;
        cin >> num;
        tree[num].push_back(i+1);
    }
    /* 计算深度 */
    calc_deep(0);
    int long_path = deep[0] - 1;
    if(long_path > L)  cout << L + 1;
    else cout << 1 + long_path + (L - long_path)/2;

}

//最简单AC 没有之一#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
	int n;
	int l;
	while (cin >> n){
		cin >> l;
		vector<int> v1(n, 0);
		v1[0] = 1;
		int temp;
		int res = 1;
		for (int i = 0; i < n - 1; i++){
			cin >> temp;
			v1[i+1] = v1[temp]+1;
			if (v1[i + 1]>res){
				res = v1[i + 1];
			}
		}
		if (res < l + 1){
			int res_temp = res + (l - res + 1) / 2;
			if (res_temp > n){
				cout << n << endl;
			}
			else{
				cout << res + (l - res + 1) / 2 << endl;
			}
			
		}
		else{
			cout << l + 1 << endl;
		}
	}
	return 0;
}

import sys
n,l=list(map(int,sys.stdin.readline().strip().split()))
parent=list(map(int,sys.stdin.readline().strip().split()))
deepLen=[0]*n
for i in range(n-1):
    deepLen[i+1]=deepLen[parent[i]]+1
maxLen=max(deepLen)
if l<maxLen:
    print(l+1)
else:
    print(maxLen+1+(l-maxLen)//2)

语言：C++ 运行时间： 4 ms 占用内存：504K 状态：答案正确
思路参考的@夭寿啦要没Offer啦，但是我使用的简单的邻接矩阵存的树，编写和理解都很简单，height函数是用来求树高度，求出树高其他的就非常简单了。
本套8道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)上，持续更新。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int height(bool adj[], int node);
int main()
{
    int l; cin >> n >> l;
    bool *adj = new bool[n*n];
    memset(adj, false, sizeof(bool)*n*n);
    int temp;
    for (int i = 1; i < n; i++) {
        cin >> temp;
        adj[temp*n + i] = true;
    }
    int h = height(adj, 0);
    cout << min(min(l + 1, (l + 1 - h) / 2 + h), n);
    return 0;
}
int height(bool adj[], int node)
{
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        if (adj[node*n + i]) {
            int temp = height(adj, i);
            maxLen = max(maxLen, temp);
        }
    }
    return maxLen + 1;
}

//其实就是求树最大深度
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    static int[] arr = null;
    public static int maxdeep(int root) {//获取最大深度
        List<Integer> list = new ArrayList<>();// 获取root节点的所有子节点、list为空，没有子节点
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == root) {
                System.out.println(root);
                list.add(i + 1);
            }
        }
        if (list.isEmpty())
            return 0;
        else {
            int max = 0;// 子数的最大深度
            //获取root所有子节点中的最大深度
            for (Integer integer : list) {
                int temp = maxdeep(integer);
                if (max < temp)
                    max = temp;
            }
            return 1 + max;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int l = scanner.nextInt();
            arr = new int[n - 1];
            for (int i = 0; i < n - 1; i++) {
                arr[i] = scanner.nextInt();
            }
            int max = Main.maxdeep(0) + 1;// 不分叉最多走的节点
            int other = n - max;// 剩余节点
            if (l <= max - 1)
                System.out.println(l + 1);
            else
                System.out.println((l - max + 1) / 2 < other ? (l - max + 1) / 2 + max : other + max);
        }
    }
}

import java.util.ArrayList;
import java.util.Scanner;

/**
 * 魔法王国一共有n个城市,编号为0~n-1号,n个城市之间的道路连接起来恰好构成一棵树。
小易现在在0号城市,每次行动小易会从当前所在的城市走到与其相邻的一个城市,小易最多能行动L次。
如果小易到达过某个城市就视为小易游历过这个城市了,小易现在要制定好的旅游计划使他能游历最多
的城市,请你帮他计算一下他最多能游历过多少个城市(注意0号城市已经游历了,游历过的城市不重复计算)。
 *输入有两行，第一行的两个整数分别为n个城市和可以走L次
 *第二行为n-1个整数   0=<parent[i] <= i+1;  parent[i] 与 i+1之间有一条道路连接
 *   0<=i <n-2
 * 5 2
    0 1 2 3
 * */
public class TripMax {
    
    public static void getStep(City city){
        for(int i = 0;i < city.list.size();i++){
            city.list.get(i).step = city.step +1; //子节点的步数等于当前父节点的步数加1
            getStep(city.list.get(i));   //有子节点的话继续回调
        }
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();  //城市数
        int L = scan.nextInt();  //行走次数
        City[] citys = new City[n];
        for(int i = 1;i<n;i++){          //从1开始
            int temp = scan.nextInt();  //i与parent[i-1]有一条道路连接
            if(citys[i] == null){
                citys[i] = new City();         
            }
            if(citys[temp] == null){
                citys[temp] = new City();
            }
            //citys[i].pre = citys[temp];
            citys[temp].list.add(citys[i]);
        }
        //计算每一个城市节点的步数,因为一开始在城市0，所以从citys[0]开始
        getStep(citys[0]);
        int maxLen =  0; //城市树的最长步数
        for(int j = 1;j <n; j++){
            if(citys[j].step > maxLen){
                maxLen = citys[j].step;
            }
        }
        
        if(maxLen >=  L){       //如果行走次数小于或等于最长步数，则直接输出 L+1（1是指一开始已游历的0号城市）
            System.out.println( L+1); 
            return ;          
        }
        //否则的话,则有以下两种情况,  根据二叉树的结构，每多走一个城市就要多花费两步
        int rest = (L - maxLen)/2 ;       //剩下可行走的次数还可以走多少个城市
        int remainingCity = n - maxLen - 1; //还没有游历过的城市个数
        //1.如果还可以游历的城市的个数大于或等于没有有游历过的城市个数，则小易可以把所有城市都游历完。
        if(rest > remainingCity){
            System.out.println(n);
            return;
        }else{   //2.否则，小易最多可以游历 (maxLen+rest+1)个城市
            System.out.println(maxLen+rest+1);
            return;
        }
    }

    static class City{
        int step;
        //City pre;
        ArrayList<City> list = new ArrayList<City>();
    }
}

	

#include<stdio.h>
#include<vector>
#include<set>
#include<string.h>
using namespace std;
vector<int> tree[105];
int Max,n,l;
void dfs(int,int);
int main(){
    int i;
    //freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&l)!=EOF){
        for(i=0;i<105;i++) tree[i].clear();
        Max=0;
        for(i=0;i<n-1;i++){
            int x;
            scanf("%d",&x);
            tree[x].push_back(i+1);
        }
        dfs(0,0);
        if(Max>=l) printf("%d\n",l+1);
        else printf("%d\n",1+(l-Max)/2+Max);
    }
}
void dfs(int x,int step){
    if(Max<step) Max=step;
    for(int i=0;i<tree[x].size();i++)
        dfs(tree[x][i],step+1);
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//城市的个数
        int L = sc.nextInt();//移动次数
        int maxLength = 0;
        int[] parent = new int[n];
        int[] depth = new int[n];
        for(int i = 1; i <= n - 1; i++){
            parent[i] = sc.nextInt();
            depth[i] = depth[parent[i]] + 1;//当前城市节点的深度等于父节点的深度加1
            if(depth[i] > maxLength) maxLength = depth[i];
        }
        if(maxLength >= L)System.out.println(L + 1);
        //如果L比最长路径大，那么最长的路径要最后走，前面无论怎么走其他分支，多走一个城市就需要2步(一来一回)。
        else System.out.println((L - maxLength) / 2 + maxLength + 1);
    }
}

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

int main(){
    int n,L;
    while(cin>>n>>L){
        vector<int> p(n,0);
        p[0]=1;
        int mDepth=p[0];
        int temp;
        for(int i=1;i<n;i++){
            cin>>temp;
            p[i]=p[temp]+1;//i号城市在树中的深度
            if(p[i]>mDepth)
                mDepth=p[i];//树的最大深度
        }
        if(L<mDepth)//行动步数小于树的最大深度
            cout<<L+1<<endl;
        else{
            int temp=mDepth+(L+1-mDepth)/2;//行动步数大于树的最大深度，有些城市需要往返
            if(temp>=n)//行动步数足以遍历所有的城市
                cout<<n<<endl;
            else
                cout<<temp<<endl;
        }
    }
    return 0;
}

import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), L = scan.nextInt();
        int parent[] = new int[n];
        int depth[] = new int[n];
        int maxDepth = 0;
        for (int i = 1; i < n; i++) {
            parent[i] = scan.nextInt();
            depth[i] = depth[parent[i]] + 1;
            if (depth[i] > maxDepth)
                maxDepth = depth[i];
        }
        scan.close();
        int count = 0;
        if (maxDepth >= L)
            count = L;
        else
            count = (L - maxDepth) / 2 + maxDepth;
        if(count >= n - 1)
            count = n - 1;
        System.out.println(count + 1);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), L = sc.nextInt();
        int[] cities = new int[n];
        for(int i = 1; i < n; i++){// 树的结构不一定从顶端顺序依次构建， 先初始化数据， 后续处理
            cities[i] = sc.nextInt(); //i为几号城市， cities[i] 为他的父节点
        }

        int maxDept = getMaxLevel(cities, 0, 1);//获取最大节点
        /*
        * 总的来说两种情况
        * 1. L行动次数比最大深度小
        * 2. L行动次数比最大深度大，其余每个城市去（除0号城市），访问的代价是2个行动步数, 但不能超过可以访问的城市数量。
        * */
        int result = (L < maxDept) ? L + 1 : Math.min(n, maxDept +  (L - maxDept + 1) / 2);
        System.out.println(result);
    }

    /**
     * 查询最大深度
     * @param cities
     * @param num
     * @param currLevel
     * @return
     */
    public static int getMaxLevel(int[] cities, int num, int currLevel){
        int maxLevel = currLevel;
        for(int i = 1; i < cities.length; i++){
            if (cities[i] == num){
                maxLevel = Math.max(maxLevel, getMaxLevel(cities, i, currLevel + 1));
            }
        }
        return maxLevel;
    }

} 

n,steps=input().split(' ')
n,steps=int(n),int(steps)
links=input().split(' ') #连接关系
depth_every=[0 for x in range(n)] #每一个城市的深度
depth_every[0]=1 #0城市的深度
max_depth=1 #树最大深度
for i in range(n-1):
    tmp=int(links[i])
    new_depth=depth_every[tmp]+1
    depth_every[i+1]=new_depth
    max_depth=max(max_depth,new_depth)
if max_depth<steps+1: 
    #可以走的步数大于树最大深度，此时必然选择先走短分支，最后走最长分支
    #走短分支必然需要返回操作，所以扣除最长分支max_depth的步数除以2取整，
    #表示额外到达的城市
    tmp=max_depth+int((steps+1-max_depth)/2)
    print(min(tmp,n))
else:
    print(steps+1)