#P18833. [COCI 2026/2027 #2] Neprijatelji

[COCI 2026/2027 #2] Neprijatelji

题目描述

有一棵以城市 11 为根的树,树上有 nn 座城市。每座城市 ii 都有一位声望为 viv_i 的骑士,声望可以为负。两位不同的骑士若所在城市的树上距离小于 33,就不能同时出席宴会。

依次处理两种事件:

  • 1 x y:把城市 xx 的骑士声望改为 yy。
  • 2 x:从以 xx 为根的子树中选取若干骑士参加宴会(可以包括 xx),使任意两位入选者的城市距离至少为 33。求总声望的最大值。允许一个人都不选,此时总声望为 00。

询问不改变声望。

输入格式

第一行两个整数 n,qn,q,分别表示城市数和事件数。第二行给出 nn 个初始声望 viv_i。接下来 n−1n-1 行,每行给出一条无向边的两个端点。最后 qq 行,每行给出一个事件。

输出格式

对每个 2 x 事件,按出现顺序输出一行最大总声望。

数据范围与评分

  • 1≤n≤2000001\le n\le 200000,1≤q≤10000001\le q\le 1000000。
  • 初始声望及修改后的声望均在 [−109,109][-10^9,10^9] 内。
  • 城市编号为 11 到 nn,至少有一次第二类事件。
  • 时间限制 3 秒,内存限制 512 MiB。
子任务 分值 额外限制
1 18 n,q≤2000n,q\le 2000
2 36 每条边均连接相邻编号,树为 1,2,…,n1,2,\ldots,n 构成的链
3 37 n,q≤100000n,q\le 100000
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