#97502 (Java) No.363 門松サイクル

• 問題: No.363 門松サイクル
• ユーザー: 37zigen
• 提出日時: 2016-06-13 11:30:06
• 言語: Java (openjdk 23)
• 結果: RE
• 実行時間: -
• コード長: 4,745 bytes
• コンパイル時間: 2,523 ms
• コンパイル使用メモリ: 80,304 KB
• 実行使用メモリ: 107,956 KB
• 最終ジャッジ日時: 2024-10-09 13:09:19
• 合計ジャッジ時間: 31,712 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

ファイルパターン	結果
sample	AC * 1 RE * 1
other	AC * 1 WA * 1 RE * 25

ソースコード

package yukicoder;

import java.util.ArrayList;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		new Main().solve();
	}

	ArrayList<Integer> edges[];
	int[] A;
	void solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		A = new int[N];
		for (int i = 0; i < N; i++)
			A[i] = sc.nextInt();
		edges = new ArrayList[N];
		for (int i = 0; i < N; i++)
			edges[i] = new ArrayList<Integer>();
		for (int i = 0; i < N - 1; i++) {
			int x = sc.nextInt() - 1;
			int y = sc.nextInt() - 1;
			edges[x].add(y);
			edges[y].add(x);
		}
		init(N);
		init2();

		int Q = sc.nextInt();
		for (int i = 0; i < Q; i++) {
			int u = sc.nextInt() - 1;
			int v = sc.nextInt() - 1;
			int lca = lca(u, v);
			if(!isKado_seq(u,lca)){
				System.out.println("NO");
			}
			else if(!isKado_seq(v,lca)){
				System.out.println("NO");
			}
			else if(!isKado(A[u],A[v],A[parent[0][v]])){
				System.out.println("NO");
			}
			else if(!isKado(A[v],A[u],A[parent[0][u]])){
				System.out.println("NO");
			}
			else if(!isKado(A[chi.get(0)],A[lca],A[chi.get(1)])){
				System.out.println("NO");
			}else{
				System.out.println("YES");
			}
		}
	}

	boolean isKado(int a, int b, int c) {
		if (a < 0 || b < 0 || c < 0)
			return false;
		if (a == b || b == c || c == a)
			return false;
		if (a < b && b > c)
			return true;
		if (a > b && b < c)
			return true;
		return false;
	}

	int MAX_LOG_V;// =(int)log2(MAX_V)+1
	int MAX_V;
	int root;// 根ノードの番号
	int parent[][];// [MAX_LOG_V + 1][MAX_V]
	// parent[k][v] 2^k回親を辿ったときに到達する頂点（根を通り過ぎたときは-1）
	int[] depth;// [MAX_V] 根からの深さ

	void init(int N) {
		// 変数の用意
		MAX_V = N;
		MAX_LOG_V = (int) (Math.log(MAX_V) / Math.log(2)) + 1;
		root = 0;
		parent = new int[MAX_LOG_V + 1][MAX_V];
		depth = new int[MAX_V];

		// parent[0]とdepthを初期化する
		dfs(root, -1, 0);
		// parentを初期化する
		for (int k = 0; k < MAX_LOG_V; k++) {
			for (int v = 0; v < MAX_V; v++) {
				if (parent[k][v] < 0) {
					parent[k + 1][v] = -1;
				} else {
					parent[k + 1][v] = parent[k][parent[k][v]];
				}
			}
		}
	}

	void dfs(int v, int p, int d) {
		parent[0][v] = p;
		depth[v] = d;
		for (int i = 0; i < edges[v].size(); i++) {
			if (edges[v].get(i) != p)
				dfs(edges[v].get(i), v, d + 1);
		}
	}

	int lca(int u, int v) {
		// uとvの深さが同じになるまで親を辿る
		if (depth[u] > depth[v]) {
			int d = u;
			u = v;
			v = d;
		}
		// depth[v]-depth[u]>=2^kとなる最小のkを求める。
		// つまりuをvと深さが同じか小さいぎりぎりのところまで親を辿る。
		for (int k = 0; k < MAX_LOG_V; k++) {
			if ((((depth[v] - depth[u]) >> k) & 1) == 1) {
				v = parent[k][v];
			}
		}
		if (u == v)
			return u;
		// uとvが衝突しないように辿る。
		for (int k = MAX_LOG_V - 1; k >= 0; k--) {
			if (parent[k][u] != parent[k][v] && parent[k][u] != -1 && parent[k][v] != -1) {
				u = parent[k][u];
				v = parent[k][v];
			}
		}
		return parent[0][u];
	}

	/*
	 * B[k]=1ならば A[k],A[k+1],A[k+2]が門松列であり、0なら門松列でない、とする。
	 * B[k]=1&&B[k+1]=1のときのみ、A[k],A[k+1],A[k+2],A[k+3]が門松列
	 * B[k]=1&&B[k+1]=1かつB[k+2]=1&&B[k+3]=1ならばA[k],A[k+1],A[k+2],A[k+3],A[k+4],A
	 * [k+5]が門松列。 
	 * C[0][k]=B[k]
	 * C[1][k]=C[0][[k]&C[0][k+1] 
	 * C[2][k]=C[1][k]&C[1][k+2]
	 * C[3][k]=C[2][k]&C[2][k+4] 
	 * C[4][k]=C[3][k]&C[3][k+8]
	 * C[v][k]=C[v-1][k]&C[v-1][k+2^(v-1)] と次々に定義する。 このとき、C[v][k]=1であることと
	 * A[k],...,A[k+2^v+2] が門松列であることは同値である。
	 */
	int[][] C;

	void init2() {
		// 変数の用意
		C = new int[MAX_LOG_V + 1][MAX_V];

		// C[0]を初期化する
		for (int i = 0; i < MAX_V; i++) {
			int p1 = parent[0][i];
			if(p1==-1)continue;
			int p2 = parent[0][p1];
			if(p2==-1)continue;
			if (isKado(A[i], A[p1], A[p2])) {
				C[0][i] = 1;
			}
		}
		// Cを初期化する
		for (int v = 0; v < MAX_LOG_V; v++) {
			for (int k = 0; k < MAX_V; k++) {
				if((k + (int) Math.pow(2, v))>=MAX_V)continue;
				C[v + 1][k] = C[v][k] & C[v][k + (int) Math.pow(2, v)];
			}
		}
	}

	boolean isKado_seq(int c, int p) {
		int d = depth[c] - (depth[p] + 2);
		if (d == -1) {
			chi.add(c);
			return true;
		}
		if (C[0][c] == 0)
			return false;
		for (int i = 0; d > 0; d >>= 1, i++) {
			if ((d & 1) == 1) {
				c = parent[i][c];
				int judge = C[i][c];
				if (judge == 0)
					return false;
			}
		}
		if (parent[0][parent[0][c]] != p)
			throw new AssertionError("c!=p");
		chi.add(parent[0][c]);
		return true;
	}

	ArrayList<Integer> chi = new ArrayList<Integer>();
}