The Flower of the Game

Do you know syllogism? blackking knows it well.

PS is a game. Trees and queries are the flowers of PS. Therefore, trees and queries are the flowers of the game.

- blackking26

A tree with $N$ vertices (a connected graph with no undirected cycles) is given. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$. Vertex $i$ has an integer weight $A_i$.

For a vertex sequence $v_1, v_2, \cdots, v_k$, if there is an edge between $v_i$ and $v_{i+1}$ and $A_{v_i} < A_{v_{i+1}}$ $(1 \le i \le k-1)$, then $v_1, v_2, \cdots, v_k$ is an increasing path of length $k$.

Find the length of the longest increasing path in the given tree, then process the following query.

• $i$ $x$: Change the weight $A_i$ of vertex $i$ to $x$, then output the length of the longest increasing path in the tree.

The first line contains the size of the tree $N$ and the number of queries $M$.

The second line contains the weights $A_i$ of each vertex, separated by spaces.

The next $N-1$ lines each contain two vertex numbers $u$ and $v$ connected by an edge.

The next $M$ lines each contain the query information $i$ and $x$.

On the first line, print the length of the longest increasing path in the given tree.

Then print the result of each of the $M$ queries on its own line, in order.

• $1 \leq N, M \leq 100,000$
• $1 \leq A_i \leq 10^{9}$
• $1 \leq u, v \leq N$
• $1 \leq i \leq N$
• $1 \leq x \leq 10^{9}$