結果
| 問題 |
No.363 門松サイクル
|
| コンテスト | |
| ユーザー |
 anta
|
| 提出日時 | 2016-04-20 17:59:22 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 81 ms / 4,000 ms |
| コード長 | 12,588 bytes |
| コンパイル時間 | 1,350 ms |
| コンパイル使用メモリ | 109,872 KB |
| 実行使用メモリ | 28,436 KB |
| 最終ジャッジ日時 | 2024-10-04 14:26:34 |
| 合計ジャッジ時間 | 3,933 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 27 |
ソースコード
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
class FastInput {
bool _end;
public:
FastInput() : _end(false) {}
operator void*() { return _end ? 0 : (void*)this; }
template<typename T>
void read_unsigned(T *res) {
T x = 0;
for(char c = skip(); '0' <= c && c <= '9'; c = gc())
x = x * 10 + (c - '0');
*res = x;
}
template<typename T>
void read_signed(T *res) {
char c = skip();
bool sign = false;
if(c == '-') sign = true, c = gc();
T x = 0;
for(; '0' <= c && c <= '9'; c = gc())
x = x * 10 + (c - '0');
*res = !sign ? x : -x;
}
void read_c_string(char *str, int *len) {
int n = 0;
for(char c = skip(); !is_delim(c); c = gc())
str[n ++] = c;
str[n] = 0;
*len = n;
}
void read_string(std::string *str) {
str->clear();
for(char c = skip(); !is_delim(c); c = gc())
*str += c;
}
void read_line(std::string *str) {
str->clear();
for(char c = gc(); c != '\n'; c = gc())
*str += c;
if(!str->empty() && (*str)[str->size() - 1] == '\r') str->resize(str->size() - 1);
}
void read_double(double *res) {
std::string buf;
read_string(&buf);
sscanf(buf.c_str(), "%lf", res);
}
void read_char(char *res) {
*res = skip();
}
void read_string_buf(char *res, int n) {
*res = skip();
}
FastInput &operator()(char &res) { read_char(&res); return *this; }
FastInput &operator()(int &res) { read_signed(&res); return *this; }
FastInput &operator()(unsigned &res) { read_unsigned(&res); return *this; }
FastInput &operator()(long long &res) { read_signed(&res); return *this; }
FastInput &operator()(unsigned long long &res) { read_unsigned(&res); return *this; }
FastInput &operator()(char *res) { int len; read_c_string(res, &len); return *this; }
FastInput &operator()(std::string &res) { read_string(&res); return *this; }
FastInput &operator()(double &res) { read_double(&res); return *this; }
template<typename T1, typename T2>
FastInput &operator()(T1 &res1, T2 &res2) {
return operator()(res1)(res2);
}
template<typename T1, typename T2, typename T3>
FastInput &operator()(T1 &res1, T2 &res2, T3 &res3) {
return operator()(res1)(res2)(res3);
}
template<typename T>
FastInput &a(T *a, int n) {
for(int i = 0; i < n; ++ i)
operator()(a[i]);
return *this;
}
template<typename T>
FastInput &operator()(vector<T> &v) {
for(size_t i = 0; i < v.size(); ++ i)
operator()(v[i]);
return *this;
}
private:
static char gc() {
#if defined(__GNUC__) && !defined(__MINGW32__)
return (char)getchar_unlocked();
#elif defined(_MSC_VER)
return (char)_getchar_nolock();
#else
return (char)getchar();
#endif
}
static bool is_delim(char c) {
return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == EOF;
}
char skip() {
if(_end) return EOF;
char c;
for(c = gc(); c != -1 && is_delim(c); c = gc());
if(c == EOF) _end = true;
return c;
}
} in;
class FastOutput {
public:
template<typename T>
void print_unsigned(T x) {
char buf[24]; int n = 0;
do buf[n ++] = x % 10, x /= 10; while(x != 0);
while(n > 0) pc('0' + buf[-- n]);
}
template<typename T>
void print_signed(T x) {
char buf[24]; int n = 0; bool sign = false;
if(x < 0) sign = true;
//depends on the -x % y behaviour
do buf[n ++] = x % 10, x /= 10; while(x != 0);
if(!sign) {
while(n > 0) pc('0' + buf[-- n]);
} else {
pc('-');
while(n > 0) pc('0' - buf[-- n]);
}
}
void print_c_string(const char *str) {
for(const char *p = str; *p; ++ p)
pc(*p);
}
void print_string(const std::string &str) {
print_c_string(str.c_str());
}
void print_double(double x, int digits) {
//|res| < 2^1024 ~ 10^308
char buf[512];
#ifdef _MSC_VER
sprintf_s(buf, "%.*f", digits, x);
#else
sprintf(buf, "%.*f", digits, x);
#endif
print_c_string(buf);
}
void print_char(char x) {
pc(x);
}
FastOutput &operator()(char x) { print_char(x); return *this; }
FastOutput &operator()(int x) { print_signed(x); return *this; }
FastOutput &operator()(unsigned x) { print_unsigned(x); return *this; }
FastOutput &operator()(long long x) { print_signed(x); return *this; }
FastOutput &operator()(unsigned long long x) { print_unsigned(x); return *this; }
FastOutput &operator()(const char *str) { print_c_string(str); return *this; }
FastOutput &operator()(const std::string &str) { print_string(str); return *this; }
FastOutput &operator()(double x) { print_double(x, 10); return *this; }
template<typename T1, typename T2>
FastOutput &operator()(T1 x1, T2 x2) { return operator()(x1)(x2); }
template<typename T1, typename T2, typename T3>
FastOutput &operator()(T1 x1, T2 x2, T3 x3) { return operator()(x1)(x2)(x3); }
template<typename T1, typename T2, typename T3, typename T4>
FastOutput &operator()(T1 x1, T2 x2, T3 x3, T4 x4) { return operator()(x1)(x2)(x3)(x4); }
private:
static void pc(char c) {
#if defined(__GNUC__) && !defined(__MINGW32__)
putchar_unlocked(c);
#elif defined(_MSC_VER)
_putchar_nolock(c);
#else
putchar(c);
#endif
}
} out;
class FastOutputN {
public:
template<typename T1>
FastOutputN &operator()(T1 x1) { out(x1)('\n'); return *this; }
template<typename T1, typename T2>
FastOutputN &operator()(T1 x1, T2 x2) { out(x1, x2)('\n'); return *this; }
template<typename T1, typename T2, typename T3>
FastOutputN &operator()(T1 x1, T2 x2, T3 x3) { out(x1, x2, x3)('\n'); return *this; }
template<typename T1, typename T2, typename T3, typename T4>
FastOutputN &operator()(T1 x1, T2 x2, T3 x3, T4 x4) { out(x1, x2, x3, x4)('\n'); return *this; }
template<typename T>
FastOutputN &a(const T *a, int n) {
for(int i = 0; i < n; ++ i) {
if(i != 0) out(' ');
out(a[i]);
}
out('\n');
return *this;
}
template<typename T>
FastOutputN &operator()(const vector<T> &v) {
for(size_t i = 0; i < v.size(); ++ i) {
if(i != 0) out(' ');
out(v[i]);
}
out('\n');
return *this;
}
} outn;
class SchieberVishkinLCA {
public:
typedef unsigned Word;
typedef int Vertex;
private:
static inline Word lowestOneBit(Word v) {
return v & (~v + 1);
}
static inline Word highestOneBitMask(Word v) {
v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;
return v >> 1;
}
std::vector<Word> indices; //Vertex -> index
std::vector<Word> maxHIndices; //Vertex -> index
std::vector<Word> ancestorHeights; //Vertex -> Word
std::vector<Vertex> pathParents; //index-1 -> Vertex
public:
void build(const std::vector<Vertex> &preorder, const std::vector<Vertex> &parents, Vertex root) {
Vertex N = static_cast<Vertex>(preorder.size());
ancestorHeights.resize(N);
maxHIndices.resize(N);
indices.resize(N);
pathParents.resize(N);
for(Vertex ix = 0; ix < N; ++ ix)
indices[preorder[ix]] = ix + 1;
for(Vertex i = 0; i < N; ++ i)
maxHIndices[i] = indices[i];
for(Vertex ix = N - 1; ix > 0; -- ix) {
Vertex v = preorder[ix], parent = parents[v];
if(lowestOneBit(maxHIndices[parent]) < lowestOneBit(maxHIndices[v]))
maxHIndices[parent] = maxHIndices[v];
}
ancestorHeights[root] = 0;
for(Vertex ix = 1; ix < N; ++ ix) {
Vertex v = preorder[ix], parent = parents[v];
ancestorHeights[v] = ancestorHeights[parent] | lowestOneBit(maxHIndices[v]);
}
pathParents[0] = root;
for(Vertex ix = 1; ix < N; ++ ix) {
Vertex v = preorder[ix], parent = parents[v];
if(maxHIndices[v] != maxHIndices[parent])
pathParents[indices[v] - 1] = parent;
else
pathParents[indices[v] - 1] = pathParents[indices[parent] - 1];
}
}
Vertex query(Vertex v, Vertex u) const {
Word Iv = maxHIndices[v], Iu = maxHIndices[u];
Word hIv = lowestOneBit(Iv), hIu = lowestOneBit(Iu);
Word hbMask = highestOneBitMask((Iv ^ Iu) | hIv | hIu);
Word j = lowestOneBit(ancestorHeights[v] & ancestorHeights[u] & ~hbMask);
Vertex x, y;
if(j == hIv) x = v;
else {
Word kMask = highestOneBitMask(ancestorHeights[v] & (j - 1));
x = pathParents[(indices[v] & ~kMask | (kMask + 1)) - 1];
}
if(j == hIu) y = u;
else {
Word kMask = highestOneBitMask(ancestorHeights[u] & (j - 1));
y = pathParents[(indices[u] & ~kMask | (kMask + 1)) - 1];
}
return indices[x] < indices[y] ? x : y;
}
};
vector<int> t_parent;
vi t_ord;
void tree_getorder(const vector<vi> &g, int root) {
int n = g.size();
t_parent.assign(n, -1);
t_ord.clear();
vector<int> stk; stk.push_back(root);
while(!stk.empty()) {
int i = stk.back(); stk.pop_back();
t_ord.push_back(i);
for(int j = (int)g[i].size() - 1; j >= 0; j --) {
int c = g[i][j];
if(t_parent[c] == -1 && c != root)
stk.push_back(c);
else
t_parent[i] = c;
}
}
}
bool isok(int a, int b, int c) {
return a != c && ((a < b && b > c) || (a > b && b < c));
}
struct LevelAncestorQuery {
int depth, i;
};
void batchedLevelAncestorQueries(int i, int p, const vector<vi> &g, vi &path, const vector<vector<LevelAncestorQuery>> &queries, vector<int> &res) {
path.push_back(i);
for(const LevelAncestorQuery &q : queries[i])
res[q.i] = (int)path.size() <= q.depth ? -1 : path[q.depth];
for(int j : g[i]) if(j != p)
batchedLevelAncestorQueries(j, i, g, path, queries, res);
path.pop_back();
}
int main() {
int N;
while(in(N)) {
vector<int> A(N);
in(A);
vector<vector<int> > g(N);
for(int i = 0; i < N - 1; ++ i) {
int u, v;
in(u, v), -- u, -- v;
g[u].push_back(v);
g[v].push_back(u);
}
tree_getorder(g, 0);
vector<bool> parok(N);
for(int ix = 0; ix < (int)t_ord.size(); ++ ix) {
int i = t_ord[ix], p = t_parent[i];
parok[i] = p == -1 || p == 0 || isok(A[t_parent[p]], A[p], A[i]);
}
vector<int> okcnt(N), depth(N);
okcnt[0] = 1;
for(int ix = 1; ix < (int)t_ord.size(); ++ ix) {
int i = t_ord[ix], p = t_parent[i];
okcnt[i] = okcnt[p] + parok[i];
depth[i] = depth[p] + 1;
}
SchieberVishkinLCA lca;
lca.build(t_ord, t_parent, 0);
int Q;
in(Q);
vector<pair<int, int>> queries(Q);
vector<int> ws(Q);
vector<vector<LevelAncestorQuery>> laqueries(N);
rep(qi, Q) {
int u; int v;
in(u, v), -- u, -- v;
queries[qi] = { u, v };
}
vector<bool> ans(Q, true);
rep(qi, Q) {
int u, v; tie(u, v) = queries[qi];
int w = lca.query(u, v);
ws[qi] = w;
int len = depth[u] + depth[v] - depth[w] * 2 + 1;
if(len <= 2) {
ans[qi] = false;
} else {
if(u != w)
laqueries[u].push_back(LevelAncestorQuery{ depth[w] + 1, qi * 2 + 0 });
if(v != w)
laqueries[v].push_back(LevelAncestorQuery{ depth[w] + 1, qi * 2 + 1 });
}
}
vector<int> cs(Q * 2, -1);
{
vector<int> path;
batchedLevelAncestorQueries(0, -1, g, path, laqueries, cs);
}
rep(qi, Q) {
if(ans[qi]) {
int u, v; tie(u, v) = queries[qi];
int w = ws[qi];
int num = 0;
int cu = cs[qi * 2 + 0], cv = cs[qi * 2 + 1];
//wが真ん中
if(w != u && w != v) {
ans[qi] = ans[qi] && isok(A[cu], A[w], A[cv]);
num += 1;
}
//u～w, v～w
rep(uv, 2) {
int t = uv == 0 ? u : v, a = uv == 0 ? cu : cv;
if(t == w) continue;
ans[qi] = ans[qi] && okcnt[t] - okcnt[a] == depth[t] - depth[a];
num += depth[t] - depth[a];
}
//追加された辺を含むもの
rep(uv, 2) {
int x = uv == 0 ? u : v, y = uv == 0 ? v : u;
int c;
if(y == w) {
c = uv == 0 ? cu : cv;
} else {
c = t_parent[y];
}
ans[qi] = ans[qi] && isok(A[x], A[y], A[c]);
num += 1;
}
assert(num == depth[u] + depth[v] - depth[w] * 2 + 1);
}
outn(ans[qi] ? "YES" : "NO");
}
}
return 0;
}