Solution-P10799

· · 题解

三角形与树 题解

题目链接

题目分析

考虑点权为什么情况时无法构成三角形。

将所有点权按照从小到大排序后记为数列 f。那么无法满足条件时，总是有 f_i\ge f_{i-1}+f_{i-2}\space(i\ge3)。其增长速度至少为斐波那契数列的增长速度。

因为点权范围在 1\sim2^{31}-1，于是当两个点之间距离大于等于 46 时，数列 f 的最后一项已经超过点权范围，故一定可以构成三角形，直接输出 1。否则使用暴力做法。

而简单路径上点的点权修改，直接上树链剖分就好了。当然也可以用简单的树上差分写法。

时间复杂度 O(n\log n+q\log^2n)，空间复杂度 O(n)。

代码展示

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[100001],l,u,v,w,x,y,tre[100001],siz[100001],top[100001],son[100001],dep[100001],fa[100001],dfn[100001],cnt;
vector<int>g[100001],m;
bool r;
inline void update(int i,int j){
    for(int k=i;k<=n;k+=k&-k){
        tre[k]^=j;
    }
    return;
}
inline int query(int i,int j=0){
    for(int k=i;k>=1;k-=k&-k){
        j^=tre[k];
    }
    return j;
}
inline void dfs(int i){
    siz[i]=1;
    son[i]=-1;
    for(int j:g[i]){
        if(dep[j]==0){
            dep[j]=dep[i]+1;
            fa[j]=i;
            dfs(j);
            siz[i]+=siz[j];
            if(son[i]==-1||siz[j]>siz[son[i]]){
                son[i]=j;
            }
        }
    }
    return;
}
inline void calc(int i,int j){
    cnt++;
    dfn[i]=cnt;
    top[i]=j;
    if(son[i]!=-1){
        calc(son[i],j);
        for(int k:g[i]){
            if(k!=son[i]&&k!=fa[i]){
                calc(k,k);
            }
        }
    }
    return;
}
signed main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=2;i<=n;i++){
        scanf("%lld%lld",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dep[1]=1;
    dfs(1);
    calc(1,1);
    for(int i=1;i<=n;i++){
        update(dfn[i],a[i]);
        update(dfn[i]+1,a[i]);
    }
    for(int i=1;i<=q;i++){
        scanf("%lld%lld%lld",&l,&u,&v);
        if(l==1){
            scanf("%lld",&w);
            while(top[u]!=top[v]){
                if(dep[top[u]]<dep[top[v]]){
                    swap(u,v);
                }
                update(dfn[top[u]],w);
                update(dfn[u]+1,w);
                u=fa[top[u]];
            }
            if(dep[u]>dep[v]){
                swap(u,v);
            }
            update(dfn[u],w);
            update(dfn[v]+1,w);
        }
        else{
            x=u;
            y=v;
            while(top[u]!=top[v]){
                if(dep[top[u]]<dep[top[v]]){
                    swap(u,v);
                }
                u=fa[top[u]];
            }
            if(dep[u]>dep[v]){
                swap(u,v);
            }
            if(dep[x]+dep[y]-2*dep[u]>=46){
                putchar('1');
            }
            else{
                u=x;
                v=y;
                if(dep[u]<dep[v]){
                    swap(u,v);
                }
                while(dep[u]>dep[v]){
                    m.push_back(query(dfn[u]));
                    u=fa[u];
                }
                while(u!=v){
                    m.push_back(query(dfn[u]));
                    m.push_back(query(dfn[v]));
                    u=fa[u];
                    v=fa[v];
                }
                m.push_back(query(dfn[u]));
                sort(m.begin(),m.end());
                if(m.size()<=2){
                    putchar('0');
                }
                else{
                    r=true;
                    for(int j=2;j<=m.size()-1;j++){
                        if(m[j]<m[j-1]+m[j-2]){
                            r=false;
                            putchar('1');
                            break;
                        }
                    }
                    if(r){
                        putchar('0');
                    }
                }
                m.clear();
            }
        }
    }
    return 0;
}

2024.8.15：修复了代码。