2021 蓝桥杯热身赛 #2

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

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

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

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

操作 11 : 减小链上的每个节点的消耗，即：对链上的每个节点 xx ，其消耗减小 ax&(−ax)a_x\&(-a_x) ，其中 &\& 是按位与运算。

操作 22 : 增大链上的每个节点的消耗，即：对链上的每个节点 xx ，若 ax≠0a_x\neq0 ，则其消耗增大 2k2^k ，其中 kk 是满足 2k≤ax<2k+12^k\le a_x < 2^{k+1} 的整数。

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

输入

输入一行一个整数 nn

接下来输入一行 nn 个整数，第 ii 个整数代表初始消耗 aia_i

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

接下来输入一行一个整数 qq ，代表事件个数

接下来输入 qq 行，每行三个整数 c,l,rc,l,r

  • 若 c=1c=1 ，对编号为 l,rl,r 两点形成的链执行操作 11
  • 若 c=2c=2 ，对编号为 l,rl,r 两点形成的链执行操作 22
  • 若 c=3c=3 ，对编号为 l,rl,r 两点形成的链执行操作 33

对 20%20\% 分数的数据，1≤n,q≤1031\le n,q\le10^3

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

输出

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

样例

标准输入 复制文本 
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
提交 1
通过 0

A B C D E F G H I J