bzoj3251 树上三角形-白红宇

bzoj3251 树上三角形

阅读量：6810 次

发布时间：2019-06-26

本文共 1407 字，大约阅读时间需要 4 分钟。

题目

给定一大小为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

分析

一道十分带劲的脑洞题。设每一个点的点权为di，如果要形成三角形，在点权排好序后至少应该有一个i满足di-2+di-1>di，那么我们考虑所有都不可能的情况，这种情况的临界情况即为对于所有的i都有di-2+di-1=di，这不由让我们想到了斐波那契公式。所以如果路径经过的点的个数多于d的范围内按斐波那契公式排列的数的个数则一定可以组成三角形。而点权范围是int，int内的斐波那契数大约有50个，所以如果两点间的路径的点数大于等于50个直接输出Y。然后我们考虑点数小于50的情况，因为这种情况下点数很少，所以我们只需暴力LCA记录路径上的点权，然后排序判断即可。

ps.我也不不知道为啥用1ll就挂了，以后还是不要用了把......

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;int fa[210000],d[210000],a[210000],dep[210000];vector
                   
                    v[210000];void dfs(int x){ int i; for(i=0;i
                    
                     dep[y]){ a[++cnt]=d[x]; x=fa[x]; if(cnt>=50){ok=1;break;} } while(x!=y){ a[++cnt]=d[x]; a[++cnt]=d[y]; x=fa[x]; y=fa[y]; if(cnt>=50){ok=1;break;} } a[++cnt]=d[x]; if(cnt>=50)ok=1; if(!ok){ sort(a+1,a+cnt+1); for(j=1;j
                     
                      a[j+2]){ ok=1; break; } } if(!ok)printf("N\n"); else printf("Y\n"); } } return 0;}

转载于:https://www.cnblogs.com/yzxverygood/p/9133260.html

你可能感兴趣的文章