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));   //根據下标獲得軍官編号
            }
        }
    }
}