2170-Marked Ancestor

問題（外部リンク）

Marked Ancestor | Aizu Online Judge

実装の概要

それぞれのノードに自分の親のidを記憶させます。今回の問題では下に向かって探索することはないので子のidは不要です。
あとはループで親を次々と巡りながらマークされたノードを探します。
なお、蟻本ではunion-find木を使う例題として紹介されていましたが、その点については特に考えなくてもACとなりました。何らかの工夫の余地はあるのかもしれません。

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			String input = br.readLine();

			if(input == null){
				break;
			}

			String[] tmpArray = input.split(" ");

			int n = Integer.parseInt(tmpArray[0]);
			int q = Integer.parseInt(tmpArray[1]);

			if(n == 0 && q == 0){
				break;
			}

			Node[] nodes = new Node[n + 1];

			nodes[1] = new Node(1, 0);
			nodes[1].marked = true;

			for(int i = 2; i <= n; i++){
				int num = Integer.parseInt(br.readLine());

				nodes[i] = new Node(i, num);
			}

			long sum = 0;

			for(int i = 0; i < q; i++){
				tmpArray = br.readLine().split(" ");
				int tmp = Integer.parseInt(tmpArray[1]);

				//指定されたノードをマークする
				if(tmpArray[0].equals("M")){
					nodes[tmp].marked = true;
				}
				//指定されたノードの祖先のidを探して加算する
				else {
					sum += nearest(nodes, tmp);
				}
			}

			System.out.println(sum);
		}
	}

	//マークされた中で最も近い祖先のidを返す
	static int nearest(Node[] nodes, int id){
		while(true){
			if(nodes[id].marked){
				return id;
			}

			id = nodes[id].parent;
		}
	}

}

class Node {
	int id;
	int parent;
	boolean marked = false;

	public Node(int id, int parent){
		this.id = id;
		this.parent = parent;
	}
}