游历魔法王国-(网易2018)

题目：游历王国一共有n个城市，编号为1~n,n个城市之间的道路连接起来恰好是一棵树，现在从0号城市出发，可以走到相邻 的城市，小易最多走L次，计算可以游历的最多城市数；
输入：
// 城市个数和行动次数
5 2
// parents数组代表城市，在(i+1)号城市和parents[i]间有一条道路连接；
0 1 2 3
输出：最多游历的城市数量
3
分析：
n个城市之间的道路连接起来恰好是一棵树；
从树深和行动次数考虑：
① 当行动次数<树深时，只需要沿着树深方向一直走就可以，此时，可以游历的最多城市数量=行动次数+1
② 当行动次数>树深时，完全走完树深不足以完成所有行动，所以此时存在回退的情况，为了得到最多的城市数量，需要尽可能的降低回退成本,故必须走最长分支，此时多余行动能经过的城市 :(n-maxLen)/2,所以经过最多的城市数量为:maxLen+(n-maxLen)/2+1
代码实现:

package com.bj.wangyi;
import java.util.Scanner;
/**
 * 游历魔法王国
 * 2<=n<=50
 * 1<=L<=100
 * 0<=parents[i]<=i
 *
 */
public class Test2 {
    @SuppressWarnings("resource")
    public static void main(String[] args) {
        String str1 = new Scanner(System.in).nextLine();
        String str2 = new Scanner(System.in).nextLine();
        String chars1 [] = str1.split(" ");
        int n = Integer.parseInt(chars1[0]);
        int L = Integer.parseInt(chars1[1]);
        String parents [] = str2.split(" ");
        int dp [] = new int[100];
        int max = 0;
        //求最大深度
        for (int i = 0; i <n-1; i++) {
            dp[i+1] = dp[Integer.parseInt(parents[i])]+1;
            max = Math.max(max, dp[i+1]);
        }
        //求最大深度和行动次数最小值
        int dd = Math.min(max, L);
        //如果行动次数大于城市个数，则取城市个数；如果城市个数大于行动走的长度，取走的长度
        int result = Math.min(n, 1+dd+(L-dd)/2);
        System.out.println(result);
    }
}

知识点：
1.问题的分析和解决方案的制定；
2.数组的使用；
3.内置函数的使用，如Math.max(),Math.min()等；