[文章目录]
Description
给你一颗带有点权(<=maxint)的树，给出m次操作，1.修改某一点的点权。2.询问u-v的路径上是否能找出三个点，使其点权大小能构成一个三角形。
脑洞特别大的一道题。
我们知道三角形任意两边之和大于第三边，所以只要选择三条边中较小的两条加起来大于另一条就说明三边可以构成三角形。
考虑不能构成三角形的序列的样子：假设将数从大到小排个序，那么对于每一个数必须大于等于在其前面两个数的和。尽可能使这个序列长，贪心方案就是使每一个数小，那么就有ai=ai-1+ai-2，这是斐波那契数列？？指数爆炸啊。。。
打个代码发现maxint里最多到第46项。那就说明只要链长>46那么一定有解。如果不是呢？？？直接暴力，O()轻松。
另外注意判断是否有解的时候加法可能爆int。转成减法是个不错的选择。
#include <cstdio>
#include <algorithm>
using namespace std;
int n,q,w[101000];
int head[101000],to[101000],nxt[101000],cnt;
inline void add(const int x,const int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int fa[101000][20],deep[101000];
void dfs(int x)
{
deep[x]=deep[fa[x][0]]+1;
for(int i=head[x];i;i=nxt[i])
dfs(to[i]);
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=17;i>=0;i--)
if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=17;i>=0;i--)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void query(int x,int y)
{
int anc=lca(x,y);
if(deep[x]+deep[y]-deep[anc]*2+1>=47) {puts("Y"); return ;}
static int c[50]; int tot=0;
while(x!=anc){c[++tot]=w[x]; x=fa[x][0];}
while(y!=anc){c[++tot]=w[y]; y=fa[y][0];}
c[++tot]=w[anc];
sort(c+1,c+tot+1);
for(int i=3;i<=tot;i++)
{
if(c[i-1]>c[i]-c[i-2])
{
puts("Y"); return ;
}
}
puts("N"); return ;
}
int main()
{
scanf("%d%d",&n,&q);
int i,j,x,y,sw;
for(i=1;i<=n;i++) scanf("%d",w+i);
for(i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y); fa[y][0]=x;
}
dfs(1);
for(i=1;i<=17;i++)
for(j=1;j<=n;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
while(q--)
{
scanf("%d%d%d",&sw,&x,&y);
if(sw) w[x]=y;
else query(x,y);
}
return 0;
}