Owaski 的神题

提交数: 1, 通过率: 0%, 平均分: 0

题目描述:

从前，有个斐波那契数列，他不甘于生活在序列上，他决定做一个有梦想的数列，于是他找到了一棵树，想生活在一棵树上。但是树告诉他，你需要解决下面的问题，才能够有资格生活在树上。

给出一颗 N 个节点的树，以 1 为根， 点 i 有权值为 Ai​​ ， 进行 M 次操作， 有四种操作：

  • 1 u v:将节点 u 的父亲改成 v。
  • 2 u v x:将节点 u 到节点 v 的简单路径上的点的权值改成 x。
  • 3 u:询问 F(Au)。
  • 4 u v:设节点 u 到节点 v 的简单路径上的点的权值分别为 B1,B2,..,Bk，询问 undefined$

其中，F(0)=0,F(1)=1,∀n≥2,F(n)=F(n−1)+F(n−2)(mod998244353)。

输入格式:

第一行两个正整数 N,M， 表示节点数和操作数。

第二行 N 个正整数表示每个点的初始权值 Ai​​。

第三行 N−1 个正整数，第 i 个正整数表示节点 i+1的父亲 fi+1， fi+1≤i。

接下来 M 行每行一个操作。

输出格式:

对于操作三和操作四，输出一行表示答案。

样例输入:

49 11
23529360 471258339 952469476 954701662 58569975 887945923 601900107 503678168 953913089 254689746 111495685 438950435 335083654 416987795 294764201 137364114 481321598 784051404 708499763 819963391 209597575 346342921 630260866 388587334 945193315 364107800 706646491 744915655 652771704 210741132 977763172 748483816 249437519 329959994 646526634 582619281 25083414 494933439 666638108 349674927 586705438 886382072 559071373 410507185 210803549 620348296 194554294 247858190 56239085
1 2 3 3 2 5 5 8 2 7 5 8 9 12 2 14 4 12 8 9 21 14 3 11 14 2 1 21 26 4 25 12 17 24 3 22 13 31 2 38 29 36 10 20 9 32 31 30
4 41 44
1 7 3
2 17 35 851698715
2 35 31 944335622
1 28 26
2 2 39 843041340
3 12
3 7
3 13
4 43 37
1 46 27

样例输出:

872528227
46427113
975410546
983117254
120066036

提示:

对于 20% 的数据，满足 N,M≤100。
对于另外 10% 的数据，满足 N,M≤1000。
对于另外 15% 的数据，满足没有操作 1, 4。
对于另外 15% 的数据，满足没有操作 4。
对于另外 15%的数据，满足没有操作 1。
对于所有数据，满足 1≤N,M≤105，1≤Ai,x≤109。

时间限制: 1000ms
空间限制: 256MB