题解 | #游历魔法王国#
游历魔法王国
http://www.nowcoder.com/practice/5be970b486ed42dbbbdbf6eaed928012
1.构建树
2.求最大深度n
3.如果步数m<n,返回m
4.如果m>n,如果走过的地方int f=(m-n)/2+n+1;
4.1如果f<总节点树k，返回f,反之，返回k
import java.util.*;
public class Main{static int maxVal=0;
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int n=in.nextInt();
int m=in.nextInt();
int[] arr=new int[n-1];
List<Node> brr=new ArrayList<Node>();
int max=0;
Node first=new Node(0);
first.flag=true;
brr.add(first);
for(int i=0;i<n-1;i++){
arr[i]=in.nextInt();
brr.add(new Node(i+1));
}
for(int i=0;i<arr.length;i++){
if(i+1>arr[i]){
brr.get(arr[i]).nexts.put(i+1,brr.get(i+1));
}else{
brr.get(i+1).nexts.put(arr[i],brr.get(arr[i]));
}
}
dfs(brr.get(0),m,max,n-1);
int res=maxVal;
if(res>=m){
System.out.println(m+1);
return;
}
int f=(m-res)/2+res+1;
if(f>n){
System.out.println(n);
return;
}
System.out.println(f);
}
public static int dfs(Node node,int sum,int max,int len){
// if(sum<=0||max==len){
// return max;
// }
if(node.nexts.size()==0){
maxVal=Math.max(max,maxVal);
return max;
}
for(int num:node.nexts.keySet()){
// if(sum<=0||max==len){
// return max;
// }
Node temp=node.nexts.get(num);
temp.flag=true;
sum-=1;
dfs(temp,sum,max+1,len);
sum-=1;
temp.flag=false;
}
return max;
}
}
class Node{
Map<Integer,Node> nexts;
boolean flag;
int val;
public Node(int val){
nexts=new HashMap<Integer,Node>();
flag=false;
this.val=val;
}
}
