25353번 - 게임의 꽃

문제

여러분은 삼단논법을 아는가? 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 ≤ i ≤ 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}$

힌트