题解：P10799 「CZOI-R1」三角形与树

0tAp · 2024-11-27 22:09:33 · 题解

题目链接：P10799 「CZOI-R1」三角形与树

做法：树链剖分+线段树。

思路：局部暴力枚举。不难想到三角形的边有以下性质 f_i<f_{i-1}+f_{i-2}，这和斐波那契很像，再观察数据范围 1\le w\le 2^{31}-1，即考虑 f_i=f_{i-1}+f_{i-2}\ge2^{31}-1 可知当 n\ge47 时一定有解，故对点数在 47 以下的进行暴力枚举判断就行。时间复杂度大概为 O(Kq\log n) 其中 K 不超过 47。

代码如下：

#include<algorithm>
#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define int long long
#define lb(a,b,n) (lower_bound((a)+1,(a)+1+(n),(b))-(a))
#define repu(i,u) for(int i=(h[u]);i;i=(ne[i]))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define debug cout<<"wwww"<<endl
#define llinf 1e18
#define inf 0x3f3f3f3f
#define pb(a) push_back((a))
#define xx return
const int N=2e5+10;

int n,q;
int h[N],e[N*2],ne[N*2],idx;
int wt[N],a[N];
namespace xx_Seg{
    #define ls (p<<1)
    #define rs (p<<1|1)
    #define mid (l+r>>1)
    struct Tree{
        int val,tag;
        #define val(p) t[p].val
        #define tag(p) t[p].tag
    }t[N*4];
    void push_down(int p){
        val(ls)^=tag(p),val(rs)^=tag(p);
        tag(ls)^=tag(p),tag(rs)^=tag(p);
        tag(p)=0;
    }
    void build(int p,int l,int r){
        if(l==r){val(p)=a[wt[l]];xx;}
        build(ls,l,mid),build(rs,mid+1,r);
    }
    void change(int p,int l,int r,int L,int R,int k){
        if(L<=l&&r<=R){val(p)^=k,tag(p)^=k;xx;}push_down(p);
        if(L<=mid)change(ls,l,mid,L,R,k);
        if(R>mid)change(rs,mid+1,r,L,R,k);
    }
    int ask(int p,int l,int r,int x){
        if(l==r)xx val(p);push_down(p);
        if(x<=mid)xx ask(ls,l,mid,x);
        else xx ask(rs,mid+1,r,x);
    }
}

namespace xx_CTT{
    int d[N],fa[N],sizt[N],son[N];
    int top[N],id[N],cnt;
    void dfs1(int u,int fath){
        d[u]=d[fath]+1;fa[u]=fath;sizt[u]=1;
        int max_son=-1;
        repu(i,u){
            int v=e[i];
            if(v==fath)continue;
            dfs1(v,u);
            sizt[u]+=sizt[v];
            if(sizt[v]>max_son)son[u]=v,max_son=sizt[v];
        }
    }
    void dfs2(int u,int topf){
        id[u]=++cnt;wt[cnt]=u;top[u]=topf;
        if(!son[u])xx;dfs2(son[u],topf);
        repu(i,u){
            int v=e[i];
            if(v==fa[u]||v==son[u])continue;
            dfs2(v,v);
        }
    }
    void change(int u,int v,int k){
        while(top[u]!=top[v]){
            if(d[top[u]]<d[top[v]])swap(u,v);
            xx_Seg::change(1,1,n,id[top[u]],id[u],k);
            u=fa[top[u]];
        }
        if(d[u]>d[v])swap(u,v);
        xx_Seg::change(1,1,n,id[u],id[v],k);
        xx;
    }
    int ask1(int u,int v){
        int now=0;
        while(top[u]!=top[v]){
            if(d[top[u]]<d[top[v]])swap(u,v);
            now+=id[u]-id[top[u]]+1;
            u=fa[top[u]];
        }
        if(d[u]>d[v])swap(u,v);
        now+=id[v]-id[u]+1;
        xx now;
    } 
    int ask2(int u,int v){
        vector<int>num;
        while(top[u]!=top[v]){
            if(d[top[u]]<d[top[v]])swap(u,v);
            rep(i,id[top[u]],id[u])num.pb(xx_Seg::ask(1,1,n,i));
            u=fa[top[u]];
        }
        if(d[u]>d[v])swap(u,v);
        rep(i,id[u],id[v])num.pb(xx_Seg::ask(1,1,n,i));
        sort(num.begin(),num.end());
        if(num.size()<3)xx 0;
        rep(i,2,num.size()-1){
            if(num[i-1]>num[i]-num[i-2])xx 1;
        }
        xx 0;
    }
}

namespace Main_xx{
    void add(int a,int b){e[++idx]=b,ne[idx]=h[a],h[a]=idx;}
    void Main(){
        cin>>n>>q;
        rep(i,1,n)cin>>a[i];
        rep(i,1,n-1){
            int u,v;cin>>u>>v;add(u,v),add(v,u);
        }
        xx_CTT::dfs1(1,0);xx_CTT::dfs2(1,1);
        xx_Seg::build(1,1,n);
        while(q--){
            int opt,u,v;cin>>opt>>u>>v;
            if(opt==1){
                int k;cin>>k;
                xx_CTT::change(u,v,k);
            }
            else{
                int ANS=xx_CTT::ask1(u,v);
                if(ANS>=47)cout<<1;
                if(ANS<3)cout<<0;
                if(ANS>=3&&ANS<=46){
                    if(xx_CTT::ask2(u,v))cout<<1;
                    else cout<<0;
                }
            }
        }
        xx;
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    Main_xx::Main();
    xx 0;
}