妙妙题集合

妙妙题指的是：

• 诈骗题

• 依赖“数字范围”的题（注意不是数据范围）

• 不依赖具体算法（得出结论后暴力可过）

#1 树上三角形

定一大小为n的有点权树，每次询问一对点(u,v)，问是否能在u到v的简单路径上取三个点权，以这三个权值为边 长构成一个三角形。同时还支持单点修改。

输入格式

第一行两个整数n、q表示树的点数和操作数

第二行n个整数表示n个点的点权

以下n-1行，每行2个整数a、b，表示a是b的父亲（以1为根的情况下）

以下q行，每行3个整数t、a、b

若t=0，则询问(a,b)

若t=1，则将点a的点权修改为b

n,q<=100000，点权范围\([1,2^{31}-1]\)

输出格式

对每个询问输出一行表示答案，“Y”表示有解，“N”表示无解。

---

注意到一个集合如果没有一组合法的，那么这个集合最差（即最大）的构造为一个斐波那契数列。又发现点权范围内的斐波那契数列的长度<50，因此断定：长度超过50的链必定合法。

// Problem: E. 树上三角形
// Contest: LibreOJ - CSP2024专题复习1
// URL: http://www.nfls.com.cn:20035/contest/2072/problem/5
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Challenger: Erica N
// ----
#include<bits/stdc++.h>

using namespace std;
#define rd read()
#define ull unsigned long long
#define int long long 
#define itn int
#define ps second 
#define pf first

int  read(){
    int x;
    cin>>x;
    return x;
}
#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() {
    cerr << endl;
}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) {
    for (auto v: a) cerr << v << ' ';
    err(x...);
}
template<typename T, typename... A>
void err(T a, A... x) {
    cerr << a << ' ';
    err(x...);
}
#else
#define dbg(...)
#endif
const int N=3e5+5;
const ull P=137;
const int INF=1e9+7;
/*

策略
可以得到三角形的条件是什么？存在权a+b>c且a<=b<=c 
c-a-b<0

太巧妙了！！

*/

#define pb push_back
int stk[N],top;
vector<int> e[N];

void add(int a,int b){
    e[a].pb(b);
    e[b].pb(a);
}


namespace LCA{
    int dep[N];int fa[N][22];
    void dfs(int x,int f){
        dep[x]=dep[f]+1;
        for(auto v:e[x]){
            if(v==f)continue;
            fa[v][0]=x;
            for(int i=1;i<=20;i++){
                fa[v][i]=fa[fa[v][i-1]][i-1];
            }
            dfs(v,x);
        }
    }

    int lca(int a,int b){
        if(dep[a]<dep[b])a^=b^=a^=b;
        for(int i=10;~i;i--){
            if(dep[fa[a][i]]>=dep[b])a=fa[a][i];
        }
        if(a==b)return a;
        for(int i=20;~i;i--){
            if(fa[a][i]!=fa[b][i]){
                a=fa[a][i];
                b=fa[b][i];
            }
        }
        return fa[a][0];
    }


    int anc;
    int getDis(int a,int b){
        anc=lca(a,b);
        return dep[a]-dep[anc]+dep[b]-dep[anc]+1;
    }

}using namespace LCA;


int w[N];

bool query(int a,int b){
    if(getDis(a,b)>50)return 1;

    cdbg(a,b);
    top=0;
    while(a!=anc){
        stk[++top]=w[a];
        a=fa[a][0];
    }
    while(b!=anc){
        stk[++top]=w[b];
        b=fa[b][0];
    }
    stk[++top]=w[anc];

    sort(stk+1,stk+top+1);
    for(int i=1;i+2<=top;i++){
        // cdbg(stk[i],stk[i+1],stk[i+2]);
        if(stk[i]+stk[i+1]>stk[i+2])return 1;
    }


    return 0;

}

signed main(){
    int n=rd,q=rd;
    for(int i=1;i<=n;i++){
        w[i]=rd;
    }

    for(int i=1;i<n;i++){
        add(rd,rd);
    }

    dfs(1,0);

    while(q--){
        int op=rd,a=rd,b=rd;
        if(op){
            w[a]=b;
        }else{
            if(query(a,b))puts("Y");
            else puts("N");
        }
    }
}