#P18841. [Croatian CPC2021] Grozne granice
[Croatian CPC2021] Grozne granice
Grozne granice
题目描述
有若干个国家,它们通过边境相连,构成一棵树。最初国家编号为 到 ,其中 号国家是克罗地亚。每个国家各派出一名代表前往 号国家开会。
代表们喜欢结伴而行:在每个国家中,所有必须经过该国的代表会先会合,再和该国自己的代表组成一支队伍,沿通往 号国家的方向继续前进。最终所有代表在 号国家会合。
进入国家 时,每名代表通常需要支付该国的关税 。该国自己的代表不需要支付本国关税。不过,进入同一个国家的各支队伍中,人数最多的一支队伍需要让其中每名代表支付双倍关税;若人数最多的队伍不止一支,则选择刚刚离开的国家编号最小的那支队伍收取双倍关税。
请支持以下三种操作:
1 v:假如现在开会,求国家 的代表从本国前往 号国家时需要支付的关税总额。2 v c:将国家 的关税修改为 。3 v c:增加一个新国家,其编号为当前尚未使用的最小正整数,关税为 ,并用一条边将它连接到国家 。
输入中的操作参数经过异或加密,需要在线解码。
输入格式
第一行包含两个整数 ,分别表示初始国家数量和操作数量。
第二行包含 个整数 。
接下来 行,每行包含两个整数 ,表示一条连接这两个国家的边。保证这些边构成一棵树。
接下来 行,每行描述一次操作。设 为最近一次类型 操作的答案;如果还没有这种操作,则 。符号 表示按位异或。
- 输入
1 v'时,实际参数为 。 - 输入
2 v' c'时,实际参数为 、。 - 输入
3 v' c'时,实际参数为 、。
输出格式
对每次类型 的操作输出一行,包含对应的关税总额。
数据范围
- ;
- 初始关税以及解码后的关税均满足 ;
- 加密后的参数满足 ;
- 保证解码后的 是操作执行前已经存在的国家编号。
样例 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 解释
前四次操作中还没有产生过查询答案,因此第四次操作的实际参数为 。
国家 的代表先进入国家 ,作为唯一进入的队伍支付双倍关税 。随后国家 的两名代表进入国家 ,他们的队伍比从国家 来的一人队伍更大,因此再次支付双倍关税 。最后,国家 的代表一起进入国家 ,仍是最大队伍,支付双倍关税 。总额为 。
第五次操作中,,实际参数为 。国家 的代表前往国家 时所在的队伍不是最大队伍,因此只支付普通关税 。