题目描述
Chavo 有一颗水晶树，树上会结出魔法水晶。包括树根在内，树一共有 个分叉的节点，其中
号节点为树根，初始状态下每一个节点都有一个生长值 。Chavo 有一根法杖，法杖可以对某个节点
释放生长法术，使得以 为根的子树的每个节点的生长值更新为
。对于每一个被更新的节点来说， 的定义都不一样，其中
是在释放法术之前被更新节点的生长值， 是在释放法术之前节点
的生长值。但是对于所有被更新的节点来说， 的递推公式都一样，是 。
Chavo 想要释放
次生长法术，每次法术都给定 ，她想问问你释放法术之后所有节点的生长值的和是多少？结果要对
取模后输出。
输入
第一行输入整数 和 ；
第二行输入 个整数，第 个整数代表第 个节点上初始值 ；
接下来
行，每一行有两个正整数 ，代表树上第 个节点和第
个节点有树杈相连；
接下来 行，每一行有 个正整数 ，如题目描述。
输出
输出一个整数代表经过所有操作后整棵树上所有节点数的和，结果要对 取模后输出。
样例输入
1
2
3
4
5
6
| 3 2
3 4 5
1 2
1 3
1 2 2
2 3 3
|
样例输出
样例说明
第一次操作时，更新
号点，对于 号点， ，更新后 号点值为 ，同理 号点值为 。
第二次操作时，更新 号点， ，更新后 号点为 。
最后求和为 。
数据范围及约定
对于 的数据， ；
对于 的数据， ；
对于 的数据， 。
时间限制与空间限制
时间限制：，空间限制：。
题解
推式子
注意，
是对于子树内每个点说的……每个点的 不一定相同，不过都是该点的权值。
树上实现子树修改和查询，搞出来个 DFS
序就变成了区间问题，线段树即可解决。
但是这什么鬼畜修改。这个类似于斐波那契数列的递推关系。
先看看
的一些值有什么规律：
如果我们定义一个类斐波那契数列 ， ， ， 就可以这样描述了：
那么就可以想到如下两种算法。
算法一
注意到修改可以分为两部分，是给这个点的子树内所有节点的权值先乘上
，再加上 。于是先做一个区间乘法，然后利用矩阵算出要加的部分，最后做一个区间加法即可。
时间复杂度为 ，空间复杂度为 。
算法二
算法一中，需要区间乘，区间加，区间覆盖，虽然很快但不好敲代码（好吧我承认其实也挺好写的……），所以考虑用一个矩阵乘法完成所有操作。
线段树中叶子节点维护的矩阵
这样构造：
其中，
为此时这个节点的的权值，线段树上非叶子节点维护的都是单位矩阵，方便之后下传矩阵。
每次修改需要乘的矩阵
是两个矩阵的乘积：
其中， 是节点 的生长值， 意义与题中相同。
那么这么乘能乘出来些什么？
为了方便，令：
发现 这个矩阵是这样的：
那么， 就是这样的：
是这样的：
更新一个节点后，矩阵就是这样的：
的位置顺利被 替代，构造成功。
那么，如何更新答案？
对于线段树矩阵，更新一个区间时
矩阵乘 ，每次查询节点
的生长值时，将这一区间矩阵下传，之后清为单位矩阵。
最后，将线段树上非叶子节点全部下传清为单位矩阵后，统计答案。即将矩阵中的
加起来。
时间复杂度为 ，空间复杂度为 。
代码见这里。