Description
给定一大小为n的有点权树，每次询问一对点(u,v)，问是否能在u到v的简单路径上取三个点权，以这三个权值为边长构成一个三角形。同时还支持单点修改。
Input
第一行两个整数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
Output
对每个询问输出一行表示答案，“Y”表示有解，“N”表示无解。
Sample Input
5 5
1 2 3 4 5
1 2
2 3
3 4
1 5
0 1 3
0 4 5
1 1 4
0 2 5
0 2 3
1 2 3 4 5
1 2
2 3
3 4
1 5
0 1 3
0 4 5
1 1 4
0 2 5
0 2 3
Sample Output
N
Y
Y
N
Y
Y
N
HINT
对于100%的数据，n,q<=100000，点权范围[1,2^31-1]
题解
感觉非常奇怪，一道结论题。
要求简单路径还有路径上每个点的权值，所以不能用倍增，只可以一个一个搞。对于所有权值，排序以下就可以最坏O（n）的情况下算出是否可构成三角形。这样做有30分。
正解需要一个结论，因为点权在int范围（c++），所以都没有三角型的情况最多为1,1,2,3,5……即斐波那契数列，然而在int范围内大约有40多50个数。所以只要点数大约大于45即可认为有三角形。在暴力中找权值是加上该判断即可。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define MAXN 100002
#define ll long long
using namespace std;
int n,m,zz,head[MAXN];
struct bian{int to,nx;} e[MAXN*2];
int h[MAXN],fa[MAXN];//2^17>10^5
ll a[MAXN],v[MAXN];
int top;
void insert(int x,int y)
{
zz++; e[zz].to=y; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].to=x; e[zz].nx=head[y]; head[y]=zz;
}
void init()
{
scanf("%d%d",&n,&m);
int i,x,y;
for(i=1;i<=n;i++) scanf("%lld",&v[i]);
for(i=1;i<n;i++)
{scanf("%d%d",&x,&y);
insert(x,y);
}
}
//------------------------------------------------------------
void dfs(int x)
{
int i,p;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(p==fa[x]) continue;
fa[p]=x; h[p]=h[x]+1;
dfs(p);
}
}
bool geta(int x,int y)
{
if(h[x]<h[y]) swap(x,y);
top=0;
for(;h[x]>h[y];x=fa[x])
{a[++top]=v[x];
if(top>45) return true;
}
while(x!=y)
{a[++top]=v[x]; x=fa[x];
a[++top]=v[y]; y=fa[y];
if(top>45) return true;
}
a[++top]=v[x];
if(top>45) return true;
sort(a+1,a+top+1);
for(int i=1;i<top-1;i++)
{if(a[i]+a[i+1]>a[i+2]) return true;}
return false;
}
void work()
{
int i,x,y,t;
for(i=1;i<=m;i++)
{scanf("%d%d%d",&t,&x,&y);
if(t==0)
{if(x==y||x==fa[y]||y==fa[x]) {printf("N\n"); continue;}
if(geta(x,y)) printf("Y\n");
else printf("N\n");
}
else v[x]=y;
}
}
int main()
{
freopen("sdtg.in","r",stdin);
freopen("sdtg.out","w",stdout);
init(); dfs(1); work();
return 0;
}