路终会有尽头，但视野总能看到更远的地方。

本文使用树链剖分维护一类动态的树形动规问题。
也可以参考immortalco的文章。

题目大意

    小 Q 是一个热爱学习的人，他经常去维基百科学习计算机科学。

    就在刚才，小 Q 认真地学习了一系列位运算符，其中按位异或的运算符$\oplus$ 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律，即 $i \oplus j = j \oplus i$。

    他发现，按位异或可以理解成被运算的数字的二进制位对应位如果相同，则结果的该位置为 $0$，否则为 $1$，例如：$1(01) \oplus 2(10) = 3(11)$。

    他还发现，按位异或可以理解成参与运算的数字的每个二进制位都进行了不进位的加法，例如：$3(11) \oplus 3(11) = 0(00)$。

    现在小 Q 有一棵 $n$ 个结点的无根树 $T$，结点依次编号为 $1$ 到 $n$，其中结点 $i$ 的权值为 $v_i$​。定义一棵树的价值为它所有点的权值的异或和，一棵树 $T$ 的连通子树就是它的一个连通子图，并且这个图也是一棵树。 小 Q 想要在这棵树上玩切树游戏，他会不断做以下两种操作：

• Change x y，将编号为 $x$ 的结点的权值修改为 $y$。
• Query k，询问有多少棵 $T$ 的非空连通子树，满足其价值恰好为 $k$。

    小 Q 非常喜（bu）欢（hui）数学，他希望你能快速回答他的问题，你能写个程序帮帮他吗？

题目大意

    询问一个棋盘上所有路径形成字符串的等价类包含的数目平方和，在指定了起点与终点后，路径一定不能不朝着终点的方向移动。
    棋盘是八连通的。

题目大意

    给定两个串A，B。请问B中有多少个非空子串和A的编辑距离不超过$K$？
    所谓“子串”，指的是B中连续的一段。不同位置的内容相同的子串算作多个。两个串之间的“编辑距离”指的是把一个串变成另一个串需要的最小的操作次数，每次操作可以插入、删除或者替换一个字符。

题目大意

    给一棵以$1$为根的树，有如下操作：

• 将一条边的边权加上$v$
• 割掉一些点，代价是点权和，询问一个点$x$的子树中叶子结点与$x$不连通的最小代价。

题目大意

    给定一个长度为$N$的数组$A[]$，求有多少对$i,j,k(1\le i\lt j\lt k\le N)$满足$A[k]-A[j]=A[j]-A[i]$。

题目大意

    万老板希望在新的智能音乐播放设备IPOOD中，实现对波文件音质性能的评定。
    离散的波文件被考虑为长度为$N$的整数序列：$A_1,A_2,\cdots,A_N$。所谓的音质性能检测，可以评定任何的一个区间范围$[L,R]$，其音质性能取决于下述评分：

$$\Big\{ \sum_{L<i<R} F[A_{i-1}+1]F[A_{i+1}-1] \Big\} \mod (10^9+7)$$

    其中$F$是可归纳定义的数列，满足$F[1]=1$，$F[2]=2$且$F[k+2]=F[k+1]+aF[k]+b$对于任何$k\ge 1$成立。其中$a$和$b$为正整系数。
    为了可以为用户提供更好的服务体验，并希望对给定的波文件进行修正优化。这一款设备中，还应该支持对波文件的修改。
对于给定的区间范围$[L,R]$，允许用户将$A[L]$至$A[R]$同时增加一，或同时减少一。

题目大意

    路由表中每一项对应了一个形如1011101?????????????????????????的规则，会匹配指定的前缀为给定形式的 ip 。当有多个规则匹配时，前缀最长的生效。同一时刻不会有多个匹配的规则的前缀一样长。
    每一个时刻，会有一条规则被加入，或者之前被加入的某条规则会过期。
    给一系列 ip，问每一个 ip 在一个给定的时间区间内匹配到的生效规则变了几次？
    例如，有一系列事件：

• Add 110
• Add 11
• Del 110
• Del 11
• Add 110

    那么,IP 地址11011101001001010101011101000010在这五个时刻之后匹配到的生效规则分别是：

• 110（第一条）
• 110（第一条）
• 11（第二条）
• 空
• 110（第三条）

    其中，在第二个事件后到第五个事件后的这段过程中，一共变了$3$次。

题目大意

    空袭，又名空中打击，是在复杂地形中常见的一种远距支援打击手段。通常由侦察兵对目标进行指示，之后最近的友方空中支援机将会发射一枚导弹打击目标。
    空袭拥有灵活性强，杀伤力大，丢失率严重等特点。
    导弹从发射到命中需要一定的时间，因此对于移动单位而言打中非常困难。因此，有经验的友军空中支援部队将会预判目标单位的移动方式，并对估计到达时的位置(而不是目标的当前位置)进行打击。
    现在我军侦察兵GloryKen正在练习如何空袭打击一只“嗜血猎食者”（又称“三级狗”）。
    这种敌方单位移动速度快且不规律，通常是侦察兵的天敌，但空袭只需一发即可消灭一只“三级狗”。
    地形可以看作是N×M的网格，有些格子有障碍无法通行。在空地上有一个敌方单位“三级狗”。
    在接下来的一段时间内，侦察兵GloryKen将会对它进行若干次空袭。具体过程可以按回合制来描述。
    三级狗的初始位置在坐标$(x,y)$，面向上下左右的某个方向。
    每个回合由如下几个阶段组成。

1. GloryKen发出一次“空袭指示”，友军空中支援部队立即发射一枚导弹。这颗导弹将会在$a_i$个回合之后命中三级狗当前位置前方$a_i$格的格子（这里的“前方”是指三级狗当前面向的方向。）。如果这个位置在地图外，那么此次空袭失效。
2. 三级狗进行一次“移动”。它可以向上下左右移动一格（不能越界，也不能到达有障碍存在的格子），也可以选择呆在当前的格子。如果进行移动，它的朝向将会变为移动的方向，否则它的朝向不变。
3. 之前所有预定于该回合到达的导弹全部同时到达在预定的位置，如果三级狗被导弹命中，它将立即死亡。导弹不会对地形造成影响，即不会破坏障碍，也不会制造障碍。

    现在，GloryKen想知道，$T$个回合的空袭之后，如果这只三级狗还存活，它的位置可能在哪里。于是，你需要求出，对于每一个格子，这只三级狗有多少种方案能够在第$T$回合恰好到达这个格子，并且存活。两个方案不同，当且
仅当某个回合三级狗的移动选择不同。

题目大意

    夏天近了，又到了恋爱的季节，小 Q 家门前的苹果树上结满了红红圆圆的苹果。

    这株苹果树是一个有着$n$个结点的有根树，其中结点被依次编号为$1$至$n$。$1$号结点为根，其余每一个结点的父结点一定是某个编号较小的结点。每一个结点上都有一些苹果，第$i$个结点上有$a_i(a_i>0)$个苹果，每取走其中一个苹果就可以得到$v_i(v_i\gt0)$的幸福度（若在这个结点取走$k\leq a_i$个苹果，则可以收获$kv_i$的幸福度）。如果在一个结点取走了至少一个苹果，则必须要在其父结点处取走至少一个苹果。

    现在，给定正整数$k$，请从树上取走若干苹果。如果总计取走了$t$个苹果，且所有取了至少一个苹果的那些结点的最大深度为$h$（这里规定根结点的深度为$1$），则要求$t-h\le k$。问最大可以收获多少的幸福度？（这些幸福度全都归属于恋爱中的小 Q）