L. Lá ele!
time limit per test
1.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

During a GruPro meeting at UFBA, an unfortunate joke started spreading through a friendship network. The network forms a tree with $$$N$$$ students, numbered from $$$1$$$ to $$$N$$$.

Each student is currently in one of two moods:

  • $$$0$$$: Calm, and will let the joke pass;
  • $$$1$$$: Suspicious, and will immediately answer "lá ele!".

When a story travels through the unique simple path between two students, every suspicious student on that path would react. However, there is an important Bahian rule: once someone says "lá ele!", everyone in the same consecutive suspicious stretch becomes protected, so no extra "lá ele!" is needed until the path reaches a calm student again.

As the meeting goes on, people may change their mood after hearing new context, remembering an older joke, or deciding that the conversation was actually harmless. Because of that, the current mood of a student is not fixed forever.

You must process two types of operations:

  • Update the mood of one student;
  • Given two students $$$u$$$ and $$$v$$$, compute how many times "lá ele!" is said along the path from $$$u$$$ to $$$v$$$.
Input

The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$2 \leq N \leq 2 \times 10^{5}$$$, $$$1 \leq Q \leq 2 \times 10^{5}$$$).

The second line contains $$$N$$$ integers $$$B_1, B_2, \dots, B_N$$$ ($$$0 \leq B_i \leq 1$$$), where $$$B_i$$$ is the initial mood of student $$$i$$$.

Each of the next $$$N-1$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq N$$$, $$$a \neq b$$$), indicating that students $$$a$$$ and $$$b$$$ are connected. It is guaranteed that these edges form a tree.

Each of the next $$$Q$$$ lines describes one operation in one of the following formats:

  • 1 u x: Set the mood of student $$$u$$$ to $$$x$$$, where $$$x \in \{0,1\}$$$;
  • 2 u v: Compute how many times "lá ele!" is said along the path from student $$$u$$$ to student $$$v$$$.
Output

For each operation of type 2, output a single integer: the number of times "lá ele!" is said along the queried path.

Examples
Input
6 6
1 0 1 0 1 1
1 2
2 3
3 4
4 5
4 6
2 1 5
2 3 6
1 4 1
2 3 6
1 2 1
2 1 5
Output
3
2
1
1
Input
5 5
0 0 0 0 0
1 2
1 3
3 4
3 5
2 2 4
1 3 1
2 2 4
1 1 1
2 2 4
Output
0
1
1