#P17801. [Ontak2024]PRO

[Ontak2024]PRO

题目描述

有一棵 nn 个顶点的无权树,顶点编号为 11 到 nn。第 vv 个顶点初始有 bvb_v 个机器人,其工厂初始每天生产 ava_v 个机器人。

观察接下来的 tt 天。每天早晨,各工厂按当前日产量生产机器人。某些天的晚上会发生一个事件,同一天至多一个:

  • 修改:将顶点 vv 的工厂日产量改为 cc,此修改从下一天早晨的生产开始生效。
  • 查询:选择一个顶点作为会场,把所有机器人临时运到那里。设当前顶点 uu 有 dud_u 个机器人,将会场选在 vv 的费用为
F(v)=∑u=1ndudist⁡(u,v),F(v)=\sum_{u=1}^{n}d_u\operatorname{dist}(u,v),

其中 dist⁡\operatorname{dist} 为树上路径的边数。查询结束后机器人立即回到原处,因此查询不会改变后续的机器人数量。

对每次查询,输出最小费用及取得该费用的最小顶点编号。

输入格式

第一行整数 g∈{0,…,6}g\in\{0,\ldots,6\},为子任务编号。

第二行三个整数 n,m,tn,m,t,为顶点数、事件数、观察天数。

第三行 nn 个整数 a1,…,ana_1,\ldots,a_n,第四行 nn 个整数 b1,…,bnb_1,\ldots,b_n。

接下来 n−1n-1 行,每行两个整数 ui,viu_i,v_i,描述树的一条边。

最后 mm 行按时间顺序描述事件:

1 ti vi ci

表示第 tit_i 天晚上把工厂 viv_i 的日产量改为 cic_i;

2 ti

表示第 tit_i 天晚上查询会场。

输出格式

对每个类型 22 的事件,输出一行两个整数 费用 顶点编号。

数据范围

  • 1≤n,m≤2×1051\le n,m\le2\times10^5,m≤t≤109m\le t\le10^9。
  • 1≤ai,bi≤1091\le a_i,b_i\le10^9。
  • 1≤ui,vi≤n1\le u_i,v_i\le n,输入边构成树;修改的顶点也是树中顶点。
  • 1≤t1<t2<⋯<tm=t1\le t_1<t_2<\cdots<t_m=t。
  • 至少有一个类型 22 的事件。

原题信息缺项: 当前官方 PDF 没有单独列出修改值 cic_i 的数值范围。本稿保留这一缺项,不擅自补成 ci≤109c_i\le10^9;若用于重新出题或制作数据,需要向原题包/出题方进一步核实。

原题提示:C++ 编译器支持有符号 __int128,该类型的常规流输入输出需要自行处理。本题要求输出精确整数,不取模。

样例 1

输入:

0
4 5 10
1 3 2 8
3 2 5 1
1 2
1 3
1 4
2 1
2 5
1 6 2 25
2 7
2 10

输出:

21 1
72 4
121 1
225 2

样例 2

输入:

0
4 2 100
3 3 3 3
7 7 7 7
1 2
2 3
3 4
2 31
2 100

输出:

400 2
1228 2

子任务

编号 附加限制 分值
1 n,m,t≤300n,m,t\le300 11
2 n,m,t≤5000n,m,t\le5000
3 n,m≤5000n,m\le5000 5
4 类型 11 的事件至多 10 个 26
5 类型 22 的事件至多 10 个 12
6 无附加限制 35