bzoj 3251 树上三角形

3251: 树上三角形

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1282 Solved: 521
[Submit][Status][Discuss]

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
n,q<=100000，点权范围[1,2^31-1]

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

Sample Output
N

我们考虑如果数字不能组成三角形？

那么将是：1,2,3,5,8,… ，可以发现这是一个斐波那契数列。由于斐波那契的性质，大于等于47项时就超过1e9了，所以如果两点之间点的个数大于等于47直接Y，否则暴力判断。

统计两点间点的数量LCA即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,q,a[N],d[N],f[N][20],h[N],lg[N];
int head[N],nex[N],to[N],tot;
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i]){
		d[to[i]]=d[x]+1;	dfs(to[i],x);
	}
}
inline int LCA(int x,int y){
	if(h[x]<h[y])	swap(x,y);
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int check(int x,int y){
	int lca=LCA(x,y),cnt=d[x]+d[y]-2*d[lca]+1;
	if(cnt>=47)	return 1;	vector<int> v; v.push_back(a[lca]);
	while(x!=lca)	v.push_back(a[x]),x=f[x][0];
	while(y!=lca)	v.push_back(a[y]),y=f[y][0];
	sort(v.begin(),v.end());
	for(int i=2;i<v.size();i++)
		if(v[i]*1ll<v[i-1]*1ll+v[i-2]*1ll)	return 1;
	return 0;
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(int i=1,a,b;i<n;i++)	scanf("%d %d",&a,&b),add(a,b);
	dfs(1,0);
	while(q--){
		int op,x,y;	scanf("%d %d %d",&op,&x,&y);
		if(op)	a[x]=y;
		else	puts(check(x,y)?"Y":"N");
	}
	return 0;
}