Background

In the past, yin and yang were created by heaven and earth, vast and profound; today, time is carved into memory, following like a shadow.
Between flowing water and falling flowers, there is playful joy in the mood of the Yin-Yang Tree; through seas turning into fields, there is an unforgettable brilliance in the Yin-Yang Memories.
Yin fish, yang fish... with the leisure of writing about the sun and moon, preserving the raccoon’s comfort, yet no longer existing...
The little raccoon CleverRaccoon, together with the last instant of yin and yang, smiles through tears...

Problem Description

Each node of a tree has $1$ yin fish or yang fish hanging on it (represented by $0, 1$ respectively). At some moment, they may transform into each other due to genetic mutation.

The little raccoon CleverRaccoon walks along a chain of this tree, carrying a basket that can hold $2$ fish. When the fish at his current node has the opposite type to some fish in the basket, he will combine these $2$ fish into $1$ yin-yang fish and eat it. If the basket is not full, he will put the fish at the current node into the basket.

There are two types of operations:

1. The yin/yang fish on a node undergoes a genetic mutation and becomes the other type of yin/yang fish.
2. Help the smart little raccoon CleverRaccoon compute: when he walks along some chain on this tree, how many yin-yang fish he can eat.

Input Format

The first line contains two positive integers $n$ and $q$, representing the number of nodes, and the total number of updates and queries.

The second line contains $n$ integers, representing the type of fish hanging on each node.

The next $n-1$ lines each contain two positive integers $u, v$, indicating that there is an edge between nodes $u$ and $v$.

The next $q$ lines are in the format 1 u or 2 u v.

If the format is 1 u, it means the fish on node $u$ undergoes genetic mutation.

If the format is 2 u v, it means querying how many yin-yang fish the little raccoon CleverRaccoon can eat on the simple path from $u$ to $v$.

Output Format

For each query, output one integer per line, representing the number of yin-yang fish that the little raccoon CleverRaccoon can eat.

9 3
1 1 1 0 1 1 0 0 0
1 2
2 3
3 4
3 5
1 6
6 7
7 8
7 9
2 9 4
1 9
2 4 9

3
2

Hint

Constraints

This problem uses bundled Subtask testdata.

• Subtask 0 (10 points): $n, q \leq 10$.
• Subtask 1 (15 points): $n, q \leq 2\times10^3$.
• Subtask 2 (15 points): the depth of the tree is less than $10^3$.
• Subtask 3 (60 points): no special constraints.

For all testdata: $1 \leq n, q \leq 10^5$.

Translated by ChatGPT 5