結果

問題 No.363 門松サイクル
ユーザー lam6er
提出日時 2025-03-26 16:02:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 535 ms / 4,000 ms
コード長 3,838 bytes
コンパイル時間 2,212 ms
コンパイル使用メモリ 200,312 KB
実行使用メモリ 49,652 KB
最終ジャッジ日時 2025-03-26 16:02:48
合計ジャッジ時間 9,403 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0