codeforces 解题报告 1006E. Military Problem 树的先序遍历（DFS）

http://codeforces.com/contest/1006/problem/E

解题思路：

1.给出军官的所属上司信息，构建出一棵树，在树的先序遍历的情况下，问对应结点能找到某个位置的下属

2.用邻接表存储每个节点的子节点信息

3. DFS 找到树先序遍历的序列 vgoal

4. sub 记录每个结点拥有的结点数量信息（包括自己），逆向遍历树计算子节点的结点数量和即可

5. map 记录每个军官在命令传递序列 vgoal 中的编号（下标）

6. 对于每次查询，如果命令传递较远（超出对应军官的子节点数量加自己）那么命令无法传达

7.否则就通过 map 获取起始军官在命令传递序列中的位置，加上传递长度，得到目标军官的下标，然后返回结果

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Vector;

public class Main {

    static Vector<Integer> vgoal = new Vector<>();
    static int num = 0;
    static Map<Integer,Integer> map = new HashMap<>();

    static void slove(Vector[] ve,int tag) {     //树的先序遍历（DFS）
        vgoal.add(tag);
        map.put(tag,num);                        //军官在传递序列中的编号
        num++;
        for(int i = 0;i < ve[tag].size();i++) {
            slove(ve, (Integer) ve[tag].get(i));
        }
    }

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(),q = sc.nextInt();
        int[] officer = new int[200010];
        Vector[] ve = new Vector[200010];
        for(int i = 1;i <= n;i++) {
            ve[i] = new Vector<Integer>();
        }
        for(int i = 2;i <= n;i++) {
            officer[i] = sc.nextInt();             //军官的上司
            ve[officer[i]].add(i);                 //军官的直接下属
        }

        slove(ve,1);                           //获取命令传递序列

        int[] sub = new int[200010];               //军官所拥有的所有下属数量（+1自己）（即命令传递有效距离）
        for(int i = n;i >= 1;i--) {
            sub[i] = 1;
            for(int j = 0;j < ve[i].size();j++) {
                int temp = (int) ve[i].get(j);     //获得子军官的编号
                sub[i] += sub[temp];               //加上子军官的下属数量（加子军官）
            }
        }

        for(int i = 1;i <= q;i++) {                 //q次穿命令
            int ocer = sc.nextInt(),subcnt = sc.nextInt();
            if(sub[ocer] < subcnt) {                //如果这个军官的命令有效传递距离小于要求，则命令不能传达
                System.out.println(-1);
            } else {                                   //能传达
                int temp = map.get(ocer) + subcnt - 1; //获得传递军官传递命令终点在传递序列中的下标
                System.out.println(vgoal.get(temp));   //根据下标获得军官编号
            }
        }
    }
}