#P18833. [COCI 2026/2027 #2] Neprijatelji
[COCI 2026/2027 #2] Neprijatelji
题目描述
有一棵以城市 为根的树,树上有 座城市。每座城市 都有一位声望为 的骑士,声望可以为负。两位不同的骑士若所在城市的树上距离小于 ,就不能同时出席宴会。
依次处理两种事件:
1 x y:把城市 的骑士声望改为 。2 x:从以 为根的子树中选取若干骑士参加宴会(可以包括 ),使任意两位入选者的城市距离至少为 。求总声望的最大值。允许一个人都不选,此时总声望为 。
询问不改变声望。
输入格式
第一行两个整数 ,分别表示城市数和事件数。第二行给出 个初始声望 。接下来 行,每行给出一条无向边的两个端点。最后 行,每行给出一个事件。
输出格式
对每个 2 x 事件,按出现顺序输出一行最大总声望。
数据范围与评分
- ,。
- 初始声望及修改后的声望均在 内。
- 城市编号为 到 ,至少有一次第二类事件。
- 时间限制 3 秒,内存限制 512 MiB。
| 子任务 | 分值 | 额外限制 |
|---|---|---|
| 1 | 18 | |
| 2 | 36 | 每条边均连接相邻编号,树为 构成的链 |
| 3 | 37 | |
| 4 | 19 | 无 |
输入输出样例
样例 1
输入
4 2
5 1 1 5
1 2
2 3
3 4
2 1
2 2
输出
10
5
样例 2
输入
5 7
-3 4 6 -2 -1
1 2
1 3
1 4
4 5
2 1
1 3 -5
2 1
1 2 -1
2 1
1 5 7
2 1
输出
6
4
0
7
样例 3
输入
8 8
3 2 4 5 1 2 6 3
1 2
1 3
2 4
2 5
3 6
6 7
6 8
2 1
2 2
1 4 -1
2 2
2 1
1 6 10
2 3
2 1
输出
11
5
2
9
10
12