結果
| 問題 |
No.363 門松サイクル
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2016-06-13 22:49:33 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 2,481 ms / 4,000 ms |
| コード長 | 8,492 bytes |
| コンパイル時間 | 2,365 ms |
| コンパイル使用メモリ | 82,840 KB |
| 実行使用メモリ | 104,288 KB |
| 最終ジャッジ日時 | 2024-10-09 13:29:19 |
| 合計ジャッジ時間 | 44,146 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 27 |
ソースコード
package yukicoder;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
new Main().solve();
// int c = 0;
// while (true) {
// new Q363().build();
// String s1 = new Q363().solve_trial();
// String s2 = "";
// try {
// s2 = new sample().run(N, A, X, Y);
// } catch (Exception e) {
// // TODO 自動生成された catch ブロック
// e.printStackTrace();
// }
// c++;
// if (!s1.equals(s2)) {
// System.out.println(N);
// for (int i = 0; i < N; i++) {
// System.out.print(A[i] + " ");
// }
// System.out.println();
// for (int i = 0; i < N - 1; i++) {
// System.out.println(X[i] + " " + Y[i]);
// }
// System.out.println(s1 + " " + s2);
// break;
// }
// System.out.println(c);
// }
// System.out.println("試行回数" + c);
}
ArrayList<Integer> edges[];
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);
chi.clear();
if (!isKado_seq(u, lca)) {
System.out.println("NO");
} else if (!isKado_seq(v, lca)) {
System.out.println("NO");
} else if (v != lca && !isKado(A[u], A[v], A[parent[0][v]])) {
System.out.println("NO");
} else if (u != lca && !isKado(A[v], A[u], A[parent[0][u]])) {
System.out.println("NO");
} else {
if (chi.size() == 1) {
if (lca != u)
chi.add(u);
else if (lca != v)
chi.add(v);
else
throw new AssertionError("lcaの一方のみがuかvであるはず");
}
if (!isKado(A[chi.get(0)], A[lca], A[chi.get(1)])) {
System.out.println("NO");
} else {
System.out.println("YES");
}
}
}
}
String solve_trial() {
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 = X[i] - 1;
int y = Y[i] - 1;
edges[x].add(y);
edges[y].add(x);
}
init(N);
init2();
int Q = 1;
for (int i = 0; i < Q; i++) {
int u = 1 - 1;
int v = 2 - 1;
int lca = lca(u, v);
chi.clear();
if (!isKado_seq(u, lca)) {
return "NO";
} else if (!isKado_seq(v, lca)) {
return "NO";
} else if (v != lca && !isKado(A[u], A[v], A[parent[0][v]])) {
return "NO";
} else if (u != lca && !isKado(A[v], A[u], A[parent[0][u]])) {
return "NO";
} else {
if (chi.size() == 1) {
if (lca != u)
chi.add(u);
else if (lca != v)
chi.add(v);
else
throw new AssertionError("lcaの一方のみがuかvであるはず");
}
if (!isKado(A[chi.get(0)], A[lca], A[chi.get(1)])) {
return "NO";
} else {
return "YES";
}
}
}
return "Error";
}
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を初期化する
bfs(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]];
}
}
}
}
class P{
int parent;
int me;
int depth;
P(int me,int parent,int depth){
this.me=me;
this.parent=parent;
this.depth=depth;
}
}
void bfs(int v, int p, int d) {
ArrayDeque<P> q=new ArrayDeque<P>();
q.add(new P(v,p,d));
while(!q.isEmpty()){
P u=q.poll();
parent[0][u.me]=u.parent;
depth[u.me]=u.depth;
for (int i = 0; i < edges[u.me].size(); i++) {
if (edges[u.me].get(i) != u.parent)
q.add(new P(edges[u.me].get(i), u.me, u.depth + 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 (parent[v][k]==-1)
continue;
C[v + 1][k] = C[v][k] & C[v][parent[v][k]];
}
}
}
boolean isKado_seq(int c, int p) {
int d = depth[c] - (depth[p] + 2);
if (d == -1) {
chi.add(c);
return true;
}
if (d == -2) {
return true;
}
if (C[0][c] == 0)
return false;
for (int i = 0; d > 0; d >>= 1, i++) {
if ((d & 1) == 1) {
int judge = C[i][c];
if (judge == 0) {
return false;
}
c = parent[i][c];
if (C[0][c] == 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>();
static int N;
static int[] A;
static int[] X;
static int[] Y;
void build() {
int max = 50000;
N = (int) (Math.random() * max) + 3;// 頂点数
A = new int[N];
X = new int[N - 1];
Y = new int[N - 1];
for (int i = 0; i < N; i++) {
A[i] = (int) (Math.random() * 10000) + 1;
}
DJSet ds = new DJSet(N);
// 0-indexedで接続されている頂点を表示
int count = 0;
while (ds.count() != 1) {
int x = (int) (Math.random() * N);
int y = (int) (Math.random() * N);
if (ds.equiv(x, y))
continue;
else {
X[count] = x + 1;
Y[count] = y + 1;
count++;
ds.setUnion(x, y);
}
}
}
class DJSet {
int n;// the number of vertices
int[] d;
DJSet(int n) {
this.n = n;
d = new int[n];
Arrays.fill(d, -1);
}
int root(int x) {
return d[x] < 0 ? x : root(d[x]);
}
boolean setUnion(int x, int y) {
x = root(x);
y = root(y);
if (x != y) {
if (x < y) {
int d = x;
x = y;
y = d;
}
// x>y
d[y] += d[x];
d[x] = y;
}
return x != y;
}
boolean equiv(int x, int y) {
return root(x) == root(y);
}
// xを含む木のNodeの数
int size(int x) {
return d[root(x)] * (-1);
}
// 連結グラフの数
int count() {
int ct = 0;
for (int u : d) {
if (u < 0)
ct++;
}
return ct;
}
}
}