「CGOI-3」灵气

Luogu

IDLGP8959

Time1000ms

Memory512MB

DifficultyP7

洛谷原创树链剖分线段树合并

ac 世界里的地牢有 $n$ 个小房间，恰好存在 $n-1$ 条过道，并且每个小房间连通。第 $i$ 个小房间生成的怪在一个时刻**最多只会存在一个**，且**伤害为 $a_i$**。为了方便刷灵气，ac 在每个过道上建了一个单向门。每一秒会发生以下几个事件之一： 1. 第 $x$ 个房间生成了一个怪。怪**不会穿墙**，只会顺着单向门方向移动。 2. 第 $x$ 个房间生成的怪被 ac 的仆从干掉了。 3. ac 想要挂机刷怪，于是他希望知道，如果从时刻 1 开始站在房间 $x$ 一直到当前时刻，受到伤害最多的一个时刻所受伤害是多少。这里定义一个时刻受到伤害为可以走到 ac 所在房间的怪的伤害值总和，“可以走到”定义为可以穿过若干条单向门到达 ac 的房间（若干可以为 $0$）。ac 非常强大，不会中途被怪打死。当然，ac 所在的位置**不会改变怪的刷新**和**仆从的行为**。 #### 简化版题面一棵树，每个点有个点权，每条边有个方向。有个集合，一开始为空，三个操作： 1. 在集合中加入一个点。 2. 删除集合中的一个点。 3. 给出一个点 $x$，询问集合中满足可以走到 $x$ 的点的点权之和的历史最大值。 ## Input 第一行，两个整数 $n,m$，分别表示房间个数和事件个数。接下来一行，共 $n$ 个整数，第 $i$ 个数表示 $i$ 房间中怪的伤害 $a_i$。接下来 $n-1$ 行，每行两个整数 $x,y$，表示 $x$ 与 $y$ 有一条过道，单向门方向为 $x\rightarrow y$ 。接下来 $m$ 行，第 $i$ 行两个整数 $fl,x$，表示第 $x$ 号房间发生了 $fl$ 号事件。对于 $fl=1$ 的操作，保证 $x$ 号房间没有怪。对于 $fl=2$ 的操作，保证 $x$ 号房间有怪。 ## Output 对每一个 $fl=3$ 的事件，输出一个整数表示答案，并用换行隔开。 [samples] ## Background >「地牢中回荡着尖叫声...」打完世花的 ac 进入地牢刷灵气…… 花后地牢十分险恶，ac 想在地牢里搭满单向门。 [![](https://cdn.luogu.com.cn/upload/image_hosting/a1ewte9n.png)](https://www.bilibili.com/video/BV1jf4y1Z7RB) ## Note #### 样例一说明第一个询问中，时刻 $1$ 存在怪的房间为 $\{4\}$，$4$ 号房间的怪可以走到 $1$ 号房间，因此答案为 $a_4=4$。第二个询问中，受到伤害最大的时刻为时刻 $1$，答案为 $a_4=4$。其中时刻 $5$ 存在怪的房间为 $\{3,5\}$，而 $5$ 号房间的怪走不到 $1$ 号房间，因此此时刻受到伤害为 $a_3=3<4$，不是最大值。第三个询问中，受到伤害最大的时刻为时刻 $5$，$3,5$ 号房间的怪均可走到 $5$，因此答案为 $a_3+a_5=8$。 --- #### 数据范围 **「本题采用捆绑测试」** 对于 $10\%$ 的数据，$n,m \leq 2000$。对于另 $10\%$ 的数据，过道 $(x,y)$ 单向门满足 $x<y$。对于另 $30\%$ 的数据，不存在 2 事件。对于 $100\%$ 的数据，$1\leq n,m \leq 2\times 10^5$，$1\leq a_i\leq10^4$。 ~~但是地牢幽魂就是穿墙怪（）（）（）~~ ~~不会真的有人会在地牢里搭满单向门吧。~~

Samples

Input #1

Output #1

4
4
8

Input #2

8 7
4 1 3 5 8 6 2 9
1 2
3 1
4 2
5 1
5 6
7 5
6 8
1 1
1 5
3 7
3 1
1 2
2 5
3 5

Output #2

0
12
8

API Response (JSON)

{
  "problem": {
    "name": "「CGOI-3」灵气",
    "description": {
      "content": "ac 世界里的地牢有 $n$ 个小房间，恰好存在 $n-1$ 条过道，并且每个小房间连通。第 $i$ 个小房间生成的怪在一个时刻**最多只会存在一个**，且**伤害为 $a_i$**。 为了方便刷灵气，ac 在每个过道上建了一个单向门。 每一秒会发生以下几个事件之一： 1. 第 $x$ 个房间生成了一个怪。怪**不会穿墙**，只会顺着单向门方向移动。 2. 第 $x$ 个房间生成的怪被 a",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8959"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "ac 世界里的地牢有 $n$ 个小房间，恰好存在 $n-1$ 条过道，并且每个小房间连通。第 $i$ 个小房间生成的怪在一个时刻**最多只会存在一个**，且**伤害为 $a_i$**。\n\n为了方便刷灵气，ac 在每个过道上建了一个单向门。\n\n每一秒会发生以下几个事件之一：\n\n1. 第 $x$ 个房间生成了一个怪。怪**不会穿墙**，只会顺着单向门方向移动。\n\n2. 第 $x$ 个房间生成的怪被 a...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments