結果

問題 No.363 門松サイクル
ユーザー btkbtk
提出日時 2016-05-24 14:36:34
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,106 bytes
コンパイル時間 1,884 ms
コンパイル使用メモリ 178,844 KB
実行使用メモリ 32,980 KB
最終ジャッジ日時 2024-10-07 05:49:21
合計ジャッジ時間 9,302 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
* Problem link
* http://yukicoder.me/problems/1024
*/

/*門松を許すな！！！！！！！！！！！！！！！！！！！！！*/

#include<bits/stdc++.h>
using namespace std;

struct INIT{INIT(){cin.tie(0);ios_base::sync_with_stdio(false);} }init;

#define rep(i,n) for(auto i=(n)*0;i<n;i++)
#define range(it,v) for(auto &it:v)
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<int> E;
typedef vector<E> Graph;
bool checkKadomatsu(int a, int b, int c) {
	return (a != c) ? ((a > b&&b < c) || (a<b&&b>c)) : false;
}
void make_tree(int v, Graph &G, VV &PP, V &D, V &A, V &prev, V& len) {
	range(u, G[v]) {
		if (u != PP[0][v]) {
			D[u] = D[v] + 1;
			PP[0][u] = v;
			prev[u] = A[v];
			if (checkKadomatsu(prev[v],A[v],A[u]))
				len[u] = len[v] + 1;
			else len[u] = (A[v] != A[u]);
			make_tree(u, G, PP, D, A, prev, len);
		}
	}
}

void build_PP(VV &PP) {
	int N = PP[0].size();
	for (int k = 0, f = 1; f; k++) {
		f = 0;
		rep(i,N)
			if (PP[k][i] >= 0)
				PP[k + 1][i] = PP[k][PP[k][i]],f = 1;
	}
}

int lca(int u, int v, V &D, VV &PP) {
	if (D[u] > D[v])swap(u, v);
	for (int k = 0, d; (d = D[v] - D[u]); k++)
		if ((d >> k) & 1)v = PP[k][v];
	if (u == v)return v;
	for (int k = PP.size() - 1; k >= 0; k--)
		if (PP[k][u] != PP[k][v])
			u = PP[k][u], v = PP[k][v];
	return PP[0][u];
}
int underroot(int root, int v, V &D, VV &PP) {
	int sz = D[v] - D[root] - 1;
	for (int k = 0; sz; k++, sz >>= 1) {
		if (sz & 1)v = PP[k][v];
	}
	return v;
}


int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	int N, Q;
	while (cin >> N) {
		V A(N);
		range(it, A)cin >> it;
		Graph g(N);
		rep(i, N - 1) {
			int x, y;
			cin >> x >> y; x--; y--;
			g[x].push_back(y);
			g[y].push_back(x);
		}

		V depth(N, 0), len(N), prev(N);
		VV parent(30, V(N, -1));
		len[0] = 0;
		prev[0] = A[0];
		make_tree(0, g, parent, depth, A, prev, len);
		build_PP(parent);


		cin >> Q;
		while (Q--) {
			int u, v, pu, pv;
			cin >> u >> v; u--; v--;
			if (depth[u] > depth[v]) swap(u, v);
			int root = lca(u, v, depth, parent);
			int l = depth[v] - depth[u];
			if (root == u) {
				if (l > len[v] || l % 2 == 0 || l < 3) {
					cout << "NO" << endl;
					continue;
				}
				pu = underroot(u, v, depth, parent);
				pv = parent[0][v];
				if (!checkKadomatsu(A[pu], A[u], A[v])) { cout << "NO" << endl; continue; }
				if (!checkKadomatsu(A[pv], A[v], A[u])) { cout << "NO" << endl; continue; }
				cout << "YES" << endl;
			}
			else {
				int lu = depth[u] - depth[root];
				int lv = depth[v] - depth[root];
				if (lu > len[u] || lv > len[v] || (lu + lv) % 2 == 0 || (lu + lv) < 3) { cout << "NO" << endl; continue; }
				pu = parent[0][u];
				pv = parent[0][v];
				if(!checkKadomatsu(A[pu],A[u],A[v])) { cout << "NO" << endl; continue; }
				if (!checkKadomatsu(A[pv], A[v], A[u])) { cout << "NO" << endl; continue; }
				pv = underroot(root, v, depth, parent);
				pu = underroot(root, u, depth, parent);
				if (!checkKadomatsu(A[pu], root, A[pv])) { cout << "NO" << endl; continue; }
				cout << "YES" << endl;
			}
		}
	}
	return 0;
}
0