「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 能吃下的阴阳鱼的条数。

输入输出样例

输入样例 #1

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

输出样例 #1

3
2

说明

**数据范围** **本题采用 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$。