結果

問題 No.363 門松サイクル
ユーザー vjudge1vjudge1
提出日時 2024-07-28 18:26:04
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 510 ms / 4,000 ms
コード長 3,838 bytes
コンパイル時間 1,958 ms
コンパイル使用メモリ 173,252 KB
実行使用メモリ 48,768 KB
最終ジャッジ日時 2024-07-28 18:26:16
合計ジャッジ時間 10,998 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 13 ms
30,848 KB
testcase_01 AC 13 ms
30,848 KB
testcase_02 AC 13 ms
30,976 KB
testcase_03 AC 13 ms
30,976 KB
testcase_04 AC 15 ms
31,104 KB
testcase_05 AC 14 ms
31,104 KB
testcase_06 AC 14 ms
30,976 KB
testcase_07 AC 15 ms
30,976 KB
testcase_08 AC 14 ms
30,976 KB
testcase_09 AC 134 ms
36,480 KB
testcase_10 AC 162 ms
36,480 KB
testcase_11 AC 237 ms
44,288 KB
testcase_12 AC 313 ms
43,008 KB
testcase_13 AC 418 ms
40,704 KB
testcase_14 AC 300 ms
39,424 KB
testcase_15 AC 217 ms
43,264 KB
testcase_16 AC 142 ms
40,448 KB
testcase_17 AC 233 ms
48,768 KB
testcase_18 AC 510 ms
41,472 KB
testcase_19 AC 287 ms
41,472 KB
testcase_20 AC 506 ms
41,600 KB
testcase_21 AC 258 ms
46,976 KB
testcase_22 AC 501 ms
41,216 KB
testcase_23 AC 217 ms
44,672 KB
testcase_24 AC 13 ms
30,976 KB
testcase_25 AC 12 ms
30,848 KB
testcase_26 AC 168 ms
48,768 KB
testcase_27 AC 170 ms
48,768 KB
testcase_28 AC 294 ms
45,184 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)
#define lowbit(x) x&(-x)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define iip pair<pair<ll,ll>,ll>
#define ppii pair<pair<ll,ll>,pair<ll,ll>>
#define fi first
#define se second
#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x
#define Full(a) memset(a,0,sizeof(a))
#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);
using namespace std;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const ll N=100100;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
struct Node{
	ll l,r;
	ll len;
	ll L1,L2;
	ll R1,R2;
	bool F;
	Node(){
		l=r=len=L1=L2=R1=R2=0;
		F=1;
	} 
	void print(){
		printf("len:%lld L1:%lld L2:%lld R1:%lld R2:%lld F:%lld\n",len,L1,L2,R1,R2,(ll)F);
	}
}X[N<<2];
ll n,q,u,v,cnt,l;
ll h[N],w[N],t[N],z[N],d[N],p[N],fa[N],dfn[N],id[N],W[N];
vector<ll> E[N];
bool check(ll a,ll b,ll c){
	if(a==b||a==c||b==c)
	  return 0;
	if(min({a,b,c})==b||max({a,b,c})==b)
	  return 1;
	return 0;
}
void add(ll x){
	if(!x)
	  return ;
	h[++l]=x;
}
void add(Node a){
	if(a.len==1)
	  add(a.L1);
	else if(a.len==2)
	  add(a.L1),add(a.R1);
	else if(a.len==3)
	  add(a.L1),add(a.L2),add(a.R1);
	else
	  add(a.L1),add(a.L2),add(a.R2),add(a.R1);
}
Node operator+(Node a,Node b){
	if(!a.len)
	  return b;
	if(!b.len)
	  return a;
	l=0;
	Node ans;
	ans.l=a.l;
	ans.r=b.r;
	ans.len=a.len+b.len;
	add(a),add(b);
	ans.L1=h[1],ans.L2=h[2];
	ans.R1=h[l],ans.R2=h[l-1];
	if(ans.len<=2)
	  ans.F=1;
	else{
		if(ans.len==3)
		  ans.F=check(h[1],h[2],h[3]);
		else{
			ans.F=a.F&b.F;
			if(a.len>1)
			  ans.F&=check(a.R2,a.R1,b.L1);
			if(b.len>1)
			  ans.F&=check(a.R1,b.L1,b.L2);
		}
	}
	return ans;
}
Node rev(Node a){
	swap(a.L1,a.R1);
	swap(a.L2,a.R2);
	return a;
}
void add(ll u,ll v){
	E[u].push_back(v);
	E[v].push_back(u);
}
void dfs1(ll u,ll f){
	p[u]=1;
	for(auto v:E[u]){
		if(v==f)
		  continue;
		fa[v]=u;
		d[v]=d[u]+1;
		dfs1(v,u);
		p[u]+=p[v];
		if(p[v]>p[z[u]])
		  z[u]=v;
	}
}
void dfs2(ll u,ll k){
	t[u]=k;
	dfn[u]=++cnt;
	id[cnt]=u;
	W[cnt]=w[u];
	if(!z[u])
	  return ;
	dfs2(z[u],k);
	for(auto v:E[u]){
		if(v==fa[u]||v==z[u])
		  continue;
		dfs2(v,v);
	}
}
void pushup(ll k){
	X[k]=X[k<<1]+X[k<<1|1];
}
void build(ll k,ll l,ll r){
	X[k].l=l,X[k].r=r;
	X[k].len=r-l+1;
	if(l==r){
		X[k].L1=X[k].R1=W[l];
		X[k].F=1;
		return ;
	}
	ll mid=(l+r)>>1;
	build(k<<1,l,mid);
	build(k<<1|1,mid+1,r);
	pushup(k);
}
Node query(ll k,ll l,ll r){
	if(X[k].l==l&&r==X[k].r)
	  return X[k];
	ll mid=(X[k].l+X[k].r)>>1;
	if(r<=mid)
	  return query(k<<1,l,r);
	else if(l>mid)
	  return query(k<<1|1,l,r);
	else
	  return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
bool query(ll u,ll v){
	bool f=0;
	Node a,b,h;
	while(t[u]!=t[v]){
		if(d[t[u]]<d[t[v]]){
			b=query(1,dfn[t[v]],dfn[v])+b;
			v=fa[t[v]];
		}
		else{
			a=query(1,dfn[t[u]],dfn[u])+a;
			u=fa[t[u]];
		}
//		a.print();
//		b.print();
	}
	if(d[u]<d[v])
	  b=query(1,dfn[u],dfn[v])+b;
	else
	  a=query(1,dfn[v],dfn[u])+a;
//	a.print();
//	b.print();
	if(a.len+b.len<=3)
	  return 0;
	h=a+rev(b);
	f=h.F;
	f&=check(h.L2,h.L1,h.R1);
	f&=check(h.L1,h.R1,h.R2);
	return f;
}
bool End;
int main(){
//	open("zigzag.in","zigzag.out");
	n=read();
	for(int i=1;i<=n;i++)
	  w[i]=read();
	for(int u,v,i=1;i<n;i++){
		u=read(),v=read();
		add(u,v);
	}
	dfs1(1,1);
	dfs2(1,1); 
	build(1,1,n);
	q=read();
	while(q--){
		u=read(),v=read();
		if(query(u,v))
		  puts("YES");
		else
		  puts("NO");
	}
	cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";
	return 0;
}
0