{"problem":{"name":"「CROI · R1」浣熊的阴阳鱼","description":{"content":"一棵树的各结点都悬挂着 $1$ 条阴鱼或阳鱼（分别用 $0,1$ 表示），它们可能在某刻由于基因突变互相转化。 小浣熊 CleverRaccoon 带着一只能装 $2$ 条鱼的篮筐在此树的某条链上行走。当他所在点上的鱼与某条筐内鱼的属性相反时，他会将这 $2$ 条鱼合成 $1$ 条阴阳鱼并吃下；在筐中没有满的条件下，他会将所在点上的鱼放入筐中。 现有两种操作： 1. 一个结点上的阴阳鱼发生基","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9555"},"statements":[{"statement_type":"Markdown","content":"一棵树的各结点都悬挂着 $1$ 条阴鱼或阳鱼（分别用 $0,1$ 表示），它们可能在某刻由于基因突变互相转化。\n\n小浣熊 CleverRaccoon 带着一只能装 $2$ 条鱼的篮筐在此树的某条链上行走。当他所在点上的鱼与某条筐内鱼的属性相反时，他会将这 $2$ 条鱼合成 $1$ 条阴阳鱼并吃下；在筐中没有满的条件下，他会将所在点上的鱼放入筐中。\n\n现有两种操作：\n\n1. 一个结点上的阴阳鱼发生基因突变，变为另一种类型的阴阳鱼。\n2. 帮助聪明的小浣熊 CleverRaccoon 求出：当他沿着这棵树上的某条链行走时，能吃下的阴阳鱼的条数。\n\n## Input\n\n第一行，两个正整数 $n$ 和 $q$，表示结点个数、修改和询问总次数。\n\n第二行 $n$ 个整数，表示每个结点上悬挂的鱼的属性。\n\n接下来 $n−1$ 行，每行两个正整数 $u,v$，表示 $u$ 和 $v$ 两个点之间有一条边。\n\n接下来 $q$ 行，格式为 `1 u` 或 `2 u v`。\n\n若格式为 `1 u`，则表示结点 $u$ 上的鱼基因突变。\n\n若格式为 `2 u v`，则表示询问小浣熊  CleverRaccoon 在从 $u$ 到 $v$ 的简单路径中能吃下的阴阳鱼的条数。\n\n## Output\n\n对于每次询问，单行输出一个整数，表示小浣熊  CleverRaccoon 能吃下的阴阳鱼的条数。\n\n[samples]\n\n## Background\n\n> 往昔，阴阳由天地所创，孕大含深；今昔，时光为记忆所刻，随行如影。\\\n流水落花间，嬉闹于阴阳树的意境；沧海桑田间，铭心于阴阳忆的缤斓。\\\n阴鱼，阳鱼……挥翰着日月的闲情，留存着浣熊的惬意，却不复存在……\\\n小浣熊 CleverRaccoon 与最后一瞬阴阳，含泪而笑……\n\n## Note\n\n**数据范围**\n\n**本题采用 Subtask 捆绑测试**。\n\n- Subtask 0（10 points）：$n,q \\leq 10$。\n- Subtask 1（15 points）：$n,q \\leq 2\\times10^3$。\n- Subtask 2（15 points）：保证树的深度小于 $10^3$。\n- Subtask 3（60 points）：无特殊限制。\n\n对于所有测试数据： $1 \\leq n,q\\leq 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9555","tags":["O2优化"],"sample_group":[["9 3\n1 1 1 0 1 1 0 0 0\n1 2\n2 3\n3 4\n3 5\n1 6\n6 7\n7 8\n7 9\n2 9 4\n1 9\n2 4 9\n","3\n2"]],"created_at":"2026-03-03 11:09:25"}}