首页 > 代码库 > 【BZOJ3251】树上三角形 暴力
【BZOJ3251】树上三角形 暴力
【BZOJ3251】树上三角形
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,231-1]
题解:正常人看到题,大概都会想到什么树剖+树套树套树什么的吧~
一种naive的做法就是,先将路径上的所有数都拿出来排序,每次只需要判断相邻的三个数能否形成三角形就行了。
仔细观察发现,如果答案为N,那么最坏的情况,就是在排完序后,任意相邻的三个数都满足x<y<z且x+y=z。这不就是斐波那契数列吗?
有什么用呢?
斐波那契数列的增长不是指数级的吗?
也就意味着一旦路径的长度>logn(实测f(47)>2147483647,所以取47或50即可),我们的结果就是Y。
难道我们还要用倍增求出路径长度吗?
朴素LCA就行辣!一旦跑了50次,就直接输出Y。否则就将所有数拿出来,用naive的做法搞一下就行了。
#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int maxn=100010;int n,m,sum,cnt;int to[maxn<<1],next[maxn<<1],head[maxn];int fa[maxn],dep[maxn],v[maxn],p[60];int rd(){ int ret=0,f=1; char gc=getchar(); while(gc<‘0‘||gc>‘9‘) {if(gc==‘-‘)f=-f; gc=getchar();} while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar(); return ret*f;}void dfs(int x){ for(int i=head[x];i!=-1;i=next[i]) fa[to[i]]=x,dep[to[i]]=dep[x]+1,dfs(to[i]);}void add(int a,int b){ to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;}int main(){ n=rd(),m=rd(); int i,j,a,b,c; for(i=1;i<=n;i++) v[i]=rd(); memset(head,-1,sizeof(head)); for(i=1;i<n;i++) a=rd(),b=rd(),add(a,b); dep[1]=1,dfs(1); for(i=1;i<=m;i++) { c=rd(),a=rd(),b=rd(),sum=0; if(c) { v[a]=b; continue; } if(dep[a]<dep[b]) swap(a,b); while(dep[a]>dep[b]&&sum<50) p[++sum]=v[a],a=fa[a]; while(a!=b&&sum<50) p[++sum]=v[a],p[++sum]=v[b],a=fa[a],b=fa[b]; p[++sum]=v[a]; if(sum>=50) { printf("Y\n"); continue; } sort(p+1,p+sum+1); for(j=3;j<=sum;j++) { if(p[j]-p[j-1]<p[j-2]) { printf("Y\n"); break; } } if(j>sum) printf("N\n"); } return 0;}
【BZOJ3251】树上三角形 暴力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。