P9555 「CROI · R1」浣熊的阴阳鱼

> 往昔，阴阳由天地所创，孕大含深；今昔，时光为记忆所刻，随行如影。\ 流水落花间，嬉闹于阴阳树的意境；沧海桑田间，铭心于阴阳忆的缤斓。\ 阴鱼，阳鱼……挥翰着日月的闲情，留存着浣熊的惬意，却不复存在……\ 小浣熊 CleverRaccoon 与最后一瞬阴阳，含泪而笑……

一棵树的各结点都悬挂着 $1$ 条阴鱼或阳鱼（分别用 $0,1$ 表示），它们可能在某刻由于基因突变互相转化。 小浣熊 CleverRaccoon 带着一只能装 $2$ 条鱼的篮筐在此树的某条链上行走。当他所在点上的鱼与某条筐内鱼的属性相反时，他会将这 $2$ 条鱼合成 $1$ 条阴阳鱼并吃下；在筐中没有满的条件下，他会将所在点上的鱼放入筐中。 现有两种操作： 1. 一个结点上的阴阳鱼发生基因突变，变为另一种类型的阴阳鱼。 2. 帮助聪明的小浣熊 CleverRaccoon 求出：当他沿着这棵树上的某条链行走时，能吃下的阴阳鱼的条数。

第一行，两个正整数 $n$ 和 $q$，表示结点个数、修改和询问总次数。 第二行 $n$ 个整数，表示每个结点上悬挂的鱼的属性。 接下来 $n−1$ 行，每行两个正整数 $u,v$，表示 $u$ 和 $v$ 两个点之间有一条边。 接下来 $q$ 行，格式为 `1 u` 或 `2 u v`。 若格式为 `1 u`，则表示结点 $u$ 上的鱼基因突变。 若格式为 `2 u v`，则表示询问小浣熊 CleverRaccoon 在从 $u$ 到 $v$ 的简单路径中能吃下的阴阳鱼的条数。

对于每次询问，单行输出一个整数，表示小浣熊 CleverRaccoon 能吃下的阴阳鱼的条数。

**数据范围** **本题采用 Subtask 捆绑测试**。 - Subtask 0（10 points）：$n,q \leq 10$。 - Subtask 1（15 points）：$n,q \leq 2\times10^3$。 - Subtask 2（15 points）：保证树的深度小于 $10^3$。 - Subtask 3（60 points）：无特殊限制。 对于所有测试数据： $1 \leq n,q\leq 10^5$。