2023 蓝桥杯热身赛

Problem P17. 异世界的魔法优化(25分)

为制作果核大陆,果冻需要编织一个精妙的法术集合。一个法术集合由许多子魔法构成。经研究,贤者禾枫发现可以通过调整子魔法的消耗改变果核大陆的各种属性。于是他们开始研究如何对异世界现有魔法进行调整。

果冻发现,法术集合能以树的形式表示,树上每个节点代表组成该法术集合的子魔法,每个节点都要消耗能量。树有 n 个节点,编号从 1n ,第 i 个节点的消耗为 a_i 。对于树上两点,定义这两点形成的链为这两点之间的最短路径。

为了调整果核大陆的各种属性并实时观测效果,果冻开始进行实验。果冻每次可以选择两个节点,对于这两个节点形成的链,果冻可以在以下 3 种操作中选择一种执行:

操作 1 : 减小链上的每个节点的消耗,即:对链上的每个节点 x ,其消耗减小 a_x\&(-a_x) ,其中 \& 是按位与运算。

操作 2 : 增大链上的每个节点的消耗,即:对链上的每个节点 x ,若 a_x\neq0 ,则其消耗增大 2^k ,其中 k 是满足 2^k\le a_x < 2^{k+1} 的整数。

操作 3 : 查询链上所有节点的消耗之和对 998244353 取模的结果。

输入

输入一行一个整数 n

接下来输入一行 n 个整数,第 i 个整数代表初始消耗 a_i

接下来输入 n-1 行,每行两个整数 u,v ,代表节点 u,v 间连有一条边

接下来输入一行一个整数 q ,代表事件个数

接下来输入 q 行,每行三个整数 c,l,r

  • c=1 ,对编号为 l,r 两点形成的链执行操作 1
  • c=2 ,对编号为 l,r 两点形成的链执行操作 2
  • c=3 ,对编号为 l,r 两点形成的链执行操作 3

20\% 分数的数据,1\le n,q\le10^3

100\% 分数的数据, 1\le n,q\le10^5,1\le u,v,l,r\le n,1\le a_i\le10^9,1\le c\le3 ,保证输入的边能够形成一棵树

输出

对于每个查询,输出一行一个整数,代表编号为 l,r 的两点形成的链上的消耗之和对 998244353 取模的结果。

样例

标准输入 复制文本
5
5 2 2 9 7
1 2
1 3
3 4
3 5
4
1 2 5
3 1 5
2 5 4
3 4 2
标准输出 复制文本
10
21

登录以提交代码。
单点时限 2 秒
内存限制 128 MB
提交 0
通过 0