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

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

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