UOJ Logo Universal Online Judge

UOJ

#576. 【ULR #1】服务器调度

附件下载 统计

在大漠中奔波数周修好电站之后,你以迅雷不及掩耳之势在三天内搭好了“跳找”的基本框架。

现在你开始思考“跳找”服务器的部署和联动问题。

“跳找”计划布置 $n$ 个服务器,编号 $1\sim n$。

这 $n$ 个服务器被 $n-1$ 条网络线路连接,即线路形成一个树形结构。树以 $1$ 号服务器为根。

每个服务器 $u$ 都有一个组别 $val_u$,组别有 $m$ 个,分别为 $1\sim m$。

每条网络线路都有一定的延时,定义 $dis(u, v)$ 为服务器 $u, v$ 之间线路延时的和,即树上 $u,v$ 间简单路径的边权和。

定义服务器 $u$ 的延时为 $\sum\limits_{k=1}^m\max\limits_{val_v=k}dis(u,v)$,也即对每个组别的最大延迟求和。

为了测试整个服务器网络的性能,需要完成下列 $q$ 个操作:

  • 修改服务器 $u$ 的组别;

  • 查询 $u$ 子树内所有服务器的延时总和。

输入格式

第一行一共三个正整数 $n, m, q$,表示服务器个数,组别数以及操作个数。

第二行一行 $n$ 个数,第 $i$ 个数 $val_i$ 表示服务器 $i$ 一开始的组别。

第三行一行 $n - 1$ 个数,第 $i$ 个数 ${fa}_{i+1}$ 表示服务器 $i + 1$ 的父亲的编号。

第四行一行 $n - 1$ 个数,第 $i$ 个数 $len_{i+1}$ 表示服务器 $i + 1$ 与父亲之间的边的边长。

下面 $q$ 行,每行开头为一个正整数 $opt_i$,表示第 $i$ 次的操作类型:

  • 若 $opt_i = 1$,那么下面紧跟两个整数 $u_i, v_i$,表示将服务器 $u_i$ 的组别修改为 $v_i$;

  • 若 $opt_i = 2$,后跟一个整数 $u_i$,表示查询 $u_i$ 子树内所有服务器的延时总和。

保证一开始及每次操作过后,每个组别都拥有至少一个服务器。

输出格式

对于每个询问,输出一行一个整数,表示该询问的答案。

样例一

input

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

output

79
40
36
44

explanation

样例一中,每个服务器的延时如图 :

样例一

样例二

input

15 4 5
2 1 3 4 1 3 3 4 2 1 2 2 1 3 2
1 1 3 2 2 1 3 4 9 10 4 8 12 10
60 39 99 85 78 41 87 70 19 8 60 60 18 3
2 1
2 2
2 3
2 4
2 5

output

16657
3820
11041
8125
1396

样例三

input

15 4 10
4 2 4 3 2 1 4 1 1 1 2 2 3 3 3 
1 1 3 3 4 2 7 8 7 6 11 9 11 6 
41 43 67 66 77 76 85 90 76 39 20 56 88 100 
1 12 1
2 1
1 7 1
2 1
1 1 1
2 1
1 13 2
2 1
1 4 2
2 1

output

23399
22389
22045
21816
21816

限制与约定

对于所有的数据,保证 $1 \leq n, q\leq 2\times10^5,\ 2m\leq n\ ,1\leq len_i\leq 200, 1 \leq fa_i \lt i, 1 \leq u_i \leq n, 1 \leq v_i,val_i \leq m$。

子任务编号 $n,q\leq$ 特殊性质 分值
$1$ $200$ $10$
$2$ $2000$ $15$
$3$ $2\times 10^5$ 不存在修改操作 $15$
$4$ $10^5$ 询问操作中 $u_i=1$ $25$
$5$ $15$
$6$ $2\times 10^5$ $20$

时间限制:$2\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载