P9555 「CROI · R1」Raccoon’s Yin-Yang Fish

> 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...

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.

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$.

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

**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