「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]
题解
若路径上有两点的点权为x，y
则若有个点z且z>abs(x-y)且z<x+y，则可以构成三角形
类似斐波那契数列1 2 3 5 8 13 。。。
发现最好情况下int范围只有不到50个点满足无法构成三角形
那么只要路径点超过50个直接输出Y，否则暴力
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<vector> #include<algorithm> #include<map> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt; int q[100005],last[100005],v[100005],deep[100005],fa[100005]; struct data{int to,next;}e[200005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; } void dfs(int x) { for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa[x]) { fa[e[i].to]=x; deep[e[i].to]=deep[x]+1; dfs(e[i].to); } } void query(int a,int b) { int top=0; while(top<50&&a!=b) { if(deep[a]>deep[b])q[++top]=v[a],a=fa[a]; else q[++top]=v[b],b=fa[b]; } q[++top]=v[a]; if(top>=50){puts("Y");return;} sort(q+1,q+top+1); for(int i=1;i<=top-2;i++) if((ll)q[i]+q[i+1]>q[i+2]){puts("Y");return;} puts("N"); } int main() { n=read();m=read(); for(int i=1;i<=n;i++)v[i]=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v);insert(v,u); } dfs(1); for(int i=1;i<=m;i++) { int t=read(),a=read(),b=read(); if(!t)query(a,b); else v[a]=b; } return 0; } |
Subscribe
计数器 9613292
OI 课件=>
OI 课件=>