게임의 꽃

여러분은 삼단논법을 아는가? blackking은 잘 알고 있다.

PS는 게임이다. 트리와 쿼리는 PS의 꽃이다. 따라서 트리와 쿼리는 게임의 꽃이다.

- blackking26

$N$개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있고, 간선은 $1$번부터 $N-1$번까지 번호가 매겨져 있다. $i$번 정점에는 정수 가중치 $A_i$가 부여되어 있다.

정점열 $v_1, v_2, \cdots, v_k$에 대해 $v_i$와 $v_{i+1}$ 사이에 간선이 있고 $A_{v_i} < A_{v_{i+1}}$ $(1 \le i \le k-1)$이면, $v_1, v_2, \cdots, v_k$는 길이가 $k$인 증가 경로이다.

주어진 트리에서 증가 경로 중 길이가 가장 긴 경로의 길이를 구한 뒤, 아래 쿼리를 처리하는 프로그램을 작성하시오.

• $i$ $x$: $i$번 정점의 가중치 $A_i$를 $x$로 바꾼 뒤, 트리에서 증가 경로 중 길이가 가장 긴 경로의 길이를 출력한다.

첫째 줄에 트리의 크기 $N$과 쿼리의 개수 $M$이 주어진다.

둘째 줄에 각 정점의 가중치 $A_i$가 공백으로 구분되어 주어진다.

이후 $N-1$개의 줄에 각 간선이 연결하는 두 정점 번호 $u$, $v$가 주어진다.

이후 $M$개의 줄에 쿼리의 정보 $i$, $x$가 주어진다.

첫 번째 줄에 주어진 트리에서 증가 경로 중 길이가 가장 긴 경로의 길이를 출력한다.

이후 $M$개의 줄에 쿼리의 결과를 한 줄에 하나씩 순서대로 출력한다.

• $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}$