#P18841. [Croatian CPC2021] Grozne granice

[Croatian CPC2021] Grozne granice

Grozne granice

题目描述

有若干个国家,它们通过边境相连,构成一棵树。最初国家编号为 11 到 nn,其中 11 号国家是克罗地亚。每个国家各派出一名代表前往 11 号国家开会。

代表们喜欢结伴而行:在每个国家中,所有必须经过该国的代表会先会合,再和该国自己的代表组成一支队伍,沿通往 11 号国家的方向继续前进。最终所有代表在 11 号国家会合。

进入国家 vv 时,每名代表通常需要支付该国的关税 cvc_v。该国自己的代表不需要支付本国关税。不过,进入同一个国家的各支队伍中,人数最多的一支队伍需要让其中每名代表支付双倍关税;若人数最多的队伍不止一支,则选择刚刚离开的国家编号最小的那支队伍收取双倍关税。

请支持以下三种操作:

  1. 1 v:假如现在开会,求国家 vv 的代表从本国前往 11 号国家时需要支付的关税总额。
  2. 2 v c:将国家 vv 的关税修改为 cc。
  3. 3 v c:增加一个新国家,其编号为当前尚未使用的最小正整数,关税为 cc,并用一条边将它连接到国家 vv。

输入中的操作参数经过异或加密,需要在线解码。

输入格式

第一行包含两个整数 n,qn,q,分别表示初始国家数量和操作数量。

第二行包含 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n。

接下来 n−1n-1 行,每行包含两个整数 ui,viu_i,v_i,表示一条连接这两个国家的边。保证这些边构成一棵树。

接下来 qq 行,每行描述一次操作。设 lastanslastans 为最近一次类型 11 操作的答案;如果还没有这种操作,则 lastans=0lastans=0。符号 ⊕\oplus 表示按位异或。

  • 输入 1 v' 时,实际参数为 v=v′⊕lastansv=v'\oplus lastans。
  • 输入 2 v' c' 时,实际参数为 v=v′⊕lastansv=v'\oplus lastans、c=c′⊕lastansc=c'\oplus lastans。
  • 输入 3 v' c' 时,实际参数为 v=v′⊕lastansv=v'\oplus lastans、c=c′⊕lastansc=c'\oplus lastans。

输出格式

对每次类型 11 的操作输出一行,包含对应的关税总额。

数据范围

  • 1≤n,q≤1051\le n,q\le10^5;
  • 初始关税以及解码后的关税均满足 0≤c≤1090\le c\le10^9;
  • 加密后的参数满足 0≤v′,c′≤10180\le v',c'\le10^{18};
  • 保证解码后的 vv 是操作执行前已经存在的国家编号。

样例 1

输入

7 5
4 6 3 4 0 5 9
2 3
3 6
4 1
5 1
1 6
7 6
2 5 0
2 6 3
3 5 4
1 2
1 16

输出

20
4

样例 2

输入

5 5
6 2 2 7 5
1 3
2 3
3 5
5 4
3 1 0
1 6
1 4
2 10 11
1 10

输出

6
14
26

样例 1 解释

前四次操作中还没有产生过查询答案,因此第四次操作的实际参数为 v=2v=2。

国家 22 的代表先进入国家 33,作为唯一进入的队伍支付双倍关税 66。随后国家 2,32,3 的两名代表进入国家 66,他们的队伍比从国家 77 来的一人队伍更大,因此再次支付双倍关税 66。最后,国家 2,3,6,72,3,6,7 的代表一起进入国家 11,仍是最大队伍,支付双倍关税 88。总额为 6+6+8=206+6+8=20。

第五次操作中,lastans=20lastans=20,实际参数为 v=16⊕20=5v=16\oplus20=5。国家 55 的代表前往国家 11 时所在的队伍不是最大队伍,因此只支付普通关税 44。