BZOJ3251:树上三角形 数学+暴力

思路:

考虑不存在三角形的情况:也就是说,任意选择三个数,总有一个最大的数不小于剩下两个数的总和.

我们想到一个的数列:斐波那契数列.

那么权值均在题目给定数据范围内的数列有多长?至多有\(log(Max)\)项.

如果超过这些项,就会在两个数之间插入某一个数,那么这三个数就是必定满足三角形条件的.(有点意识流)

总之如果总共有不超过\(log(Max)\)个数暴力判定,否则直接输出\(Y\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
int w[N];
 
int pa[N][16],dep[N];
inline void dfs(int x,int fa){
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)dep[end[j]]=dep[x]+1,pa[end[j]][0]=x,dfs(end[j],x);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=15;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=15;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
 
int seq[51],id;
 
inline bool judge(int a,int b,int c){
    long long A=a,B=b,C=c;
    return A+B>C&&B+C>A&&A+C>B;
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j,k;for(i=1;i<=n;++i)scanf("%d",&w[i]);
     
    int a,b;for(i=1;i<n;++i)scanf("%d%d",&a,&b),make(a,b);
     
    dep[1]=1,dfs(1,-1);
    for(j=1;j<=15;++j)for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
     
    int t;
    while(m--){
        scanf("%d%d%d",&t,&a,&b);
        if(t==0){
            int Lca=lca(a,b),nums=dep[a]+dep[b]-2*dep[Lca]+1;
            if(nums<=40){
                for(id=0;a!=Lca;a=pa[a][0])seq[++id]=w[a];
                for(;b!=Lca;b=pa[b][0])seq[++id]=w[b];
                seq[++id]=w[Lca];
                bool ok=0;
                for(i=1;i<=id;++i)for(j=i+1;j<=id;++j)for(k=j+1;k<=id;++k)if(judge(seq[i],seq[j],seq[k]))ok=1;
                if(ok)puts("Y");else puts("N");
            }else puts("Y");
        }else w[a]=b;
    }
     
    return 0;
}