「CROI · R1」浣熊的阴阳鱼

Luogu

IDLGP9555

Time1000ms

Memory512MB

DifficultyP6

O2优化

一棵树的各结点都悬挂着 $1$ 条阴鱼或阳鱼（分别用 $0,1$ 表示），它们可能在某刻由于基因突变互相转化。小浣熊 CleverRaccoon 带着一只能装 $2$ 条鱼的篮筐在此树的某条链上行走。当他所在点上的鱼与某条筐内鱼的属性相反时，他会将这 $2$ 条鱼合成 $1$ 条阴阳鱼并吃下；在筐中没有满的条件下，他会将所在点上的鱼放入筐中。现有两种操作： 1. 一个结点上的阴阳鱼发生基因突变，变为另一种类型的阴阳鱼。 2. 帮助聪明的小浣熊 CleverRaccoon 求出：当他沿着这棵树上的某条链行走时，能吃下的阴阳鱼的条数。 ## Input 第一行，两个正整数 $n$ 和 $q$，表示结点个数、修改和询问总次数。第二行 $n$ 个整数，表示每个结点上悬挂的鱼的属性。接下来 $n−1$ 行，每行两个正整数 $u,v$，表示 $u$ 和 $v$ 两个点之间有一条边。接下来 $q$ 行，格式为 `1 u` 或 `2 u v`。若格式为 `1 u`，则表示结点 $u$ 上的鱼基因突变。若格式为 `2 u v`，则表示询问小浣熊 CleverRaccoon 在从 $u$ 到 $v$ 的简单路径中能吃下的阴阳鱼的条数。 ## Output 对于每次询问，单行输出一个整数，表示小浣熊 CleverRaccoon 能吃下的阴阳鱼的条数。 [samples] ## Background > 往昔，阴阳由天地所创，孕大含深；今昔，时光为记忆所刻，随行如影。\ 流水落花间，嬉闹于阴阳树的意境；沧海桑田间，铭心于阴阳忆的缤斓。\ 阴鱼，阳鱼……挥翰着日月的闲情，留存着浣熊的惬意，却不复存在……\ 小浣熊 CleverRaccoon 与最后一瞬阴阳，含泪而笑…… ## Note **数据范围** **本题采用 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$。

Samples

Input #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

Output #1

3
2

API Response (JSON)

{
  "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. 一个结点上的阴阳鱼发生基...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments