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

Y

Y

N

Solution

考虑对于一个询问的一个树链，如果我们自己构造，让他不含三角形我们会怎么构造：

肯定是像$1,2,3,5,8,13$一样，类似斐波那契数列。

而斐波那契又是增长非常快的，所以当询问的树链长度超过一个值(我设的$50$个点)就肯定$Y$，否则就暴力。

Code

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define N (100009) 7 using namespace std; 8  9 struct Edge{
   int to,next;}edge[N<<2];10 int n,q,a[N],f[N][18],Depth[N];11 int head[N],num_edge;12 vector
          
           v;13 14 inline int read()15 {16 int x=0,w=1; char c=getchar();17 while (c<'0' || c>'9') { if (c=='-') w=-1; c=getchar();}18 while (c>='0' && c<='9') x=x*10+c-'0', c=getchar();19 return x*w;20 }21 22 void add(int u,int v)23 {24 edge[++num_edge].to=v;25 edge[num_edge].next=head[u];26 head[u]=num_edge;27 }28 29 void DFS(int x,int fa)30 {31 f[x][0]=fa; Depth[x]=Depth[fa]+1;32 for (int i=1; i<=17; ++i)33 f[x][i]=f[f[x][i-1]][i-1];34 for (int i=head[x]; i; i=edge[i].next)35 if (edge[i].to!=fa) DFS(edge[i].to,x);36 }37 38 int LCA(int x,int y)39 {40 if (Depth[x]
           
            =0; --i)42 if (Depth[f[x][i]]>=Depth[y]) x=f[x][i];43 if (x==y) return x;44 for (int i=17; i>=0; --i)45 if (f[x][i]!=f[y][i]) x=f[x][i], y=f[y][i];46 return f[x][0];47 }48 49 void Solve(int x,int y,int lca)50 {51 v.clear();52 while (x!=lca) v.push_back(a[x]), x=f[x][0];53 while (y!=lca) v.push_back(a[y]), y=f[y][0];54 v.push_back(a[lca]);55 sort(v.begin(),v.end());56 for (int i=1,s=v.size(); i
            
             v[i+1]) {puts("Y"); return;}58 puts("N");59 }60 61 int main()62 {63 n=read(); q=read();64 for (int i=1; i<=n; ++i) a[i]=read();65 for (int i=1; i<=n-1; ++i)66 {67 int u=read(),v=read();68 add(u,v); add(v,u);69 }70 DFS(1,0);71 while (q--)72 {73 int opt=read(),x=read(),y=read();74 if (opt==0)75 {76 int lca=LCA(x,y);77 if (Depth[x]-Depth[lca]+Depth[y]-Depth[lca]+1>50) puts("Y");78 else Solve(x,y,lca);79 }80 else a[x]=y;81 }82 }