HH 是个喜欢变化的人，所以他不会立刻沿着刚刚走来的路走回。 又因为 HH 是个喜欢变化的人，所以他每天走过的路径都不完全一样，他想知道他究竟有多少种散步的方法。

现在给你学校的地图（假设每条路的长度都是一样的都是 $1$ ），问长度为 $t$ ，从给定地点 $A$ 走到给定地点 $B$ 共有多少条符合上述条件的路径。

有一个无向图 $G$ ，每个点有个权值，每条边有一个颜色。这个无向图满足以下两个条件：

• 对于任意节点连出去的边中，相同颜色的边不超过两条。
• 图中不存在同色的环，同色的环指相同颜色的边构成的环。

在这个图上，你要支持以下三种操作：

• 修改一个节点的权值。
• 修改一条边的颜色。
• 查询由颜色 $c$ 的边构成的图中， $u$ 到节点 $v$ 之间的简单路径上的节点的权值的最大值。

对于 100% 的数据，保证颜色不多于 $10$ 种。

简单版题意：

给定一个长度为 $n$ 的字符串，和一个长度为 $n$ 的数列 $\{a_n\}$ ，求对于 $r$ 从 $0$ 到 $n-1$ ，所有满足 $1 \leq p < q \leq n$ 且 $lcp(p,q) \geq r$ 的数对个数以及满足上述条件的数对中 $a_p \times a_q$ 的最大值。（ $a_i$ 可以为负数）

现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有 $n$ 个叶子节点，满足这些权值为 $1...n$ 的一个排列)。可以任意交换每个非叶子节点的左右孩子。
要求进行一系列交换，使得最终所有叶子节点的权值按照前序遍历序写出来，逆序对个数最少。

有 $m$ 个骑士攻占 $n$ 个城池。除 $1$ 号城池外，城池 $i$ 会受到另一座城池 $f_i$ 的管辖，其中 $f_i < i$。也就是说，所有城池构成了一棵有根树。第 $i$ 个骑士的初始战斗力为 $s_i$，第一个攻击的城池为 $c_i$。

每个城池有一个防御值 $h_i$，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力将发生变化，然后继续攻击管辖这座城池的城池，直到占领 $1$ 号城池，或牺牲为止。

除 $1$ 号城池外，每个城池 $i$ 会给出一个战斗力变化参数 $a_i$;$v_i$。若 $a_i = 0$，攻占城池 $i$ 以后骑士战斗力会增加 $v_i$；若 $a_i = 1$，攻占城池 $i$ 以后，战斗力会乘以 $v_i$。注意每个骑士是单独计算的。也就是说一个骑士攻击一座城池，不管结果如何，均不会影响其他骑士攻击这座城池的结果。

对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。

给定一棵有根树，每个点有一个代价 $C_i$ ，权值 $L_i$ ，要求从这个树某个节点 $k$ 的子树（包含该节点）选取若干个节点，使得选取节点的个数乘上节点 $k$ 的权值最大，且这若干个节点的代价和不超过给定的限制 $M$ 。

一个无向连通图，顶点从 $1$ 编号到 $N$ ，边从 $1$ 编号到 $M$ 。 小 Z 在该图上进行随机游走，初始时小 Z 在 $1$ 号顶点，每一步小 Z 以相等的概率随机选 择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小 Z 到达 N 号顶点时游走结束，总分为所有获得的分数之和。 现在，请你对这 $M$ 条边进行编号，使得小 Z 获得的总分的期望值最小。

题面以图片显示，请点击“阅读全文”查看。

Y901 高速公路是一条由 $N-1$ 段路以及 $N$ 个收费站组成的东西向的链，我们按照由西向东的顺序将收费站依次编号为 $1 \sim N$ ，从收费站 $i$ 行驶到 $i+1$ (或从 $i+1$ 行驶到 $i$ )需要收取 $V_i$ 的费用。高速路刚建成时所有的路段都是免费的。

政府部门根据实际情况，会不定期地对连续路段的收费标准进行调整，根据政策涨价或降价。

求对于给定的 $l,r(l < r)$ ，在第 $l$ 个到第 $r$ 个收费站里等概率随机取出两个不同的收费站 $a$ 和 $b$ ，那么从 $a$ 行驶到 $b$ 将期望花费多少费用呢?

给出 $n$ 个数 $q_i$ ，给出 $F_j$ 定义为：

令 $E_i = \frac{F_i}{q_i}$ ，求 $E_i$ 的值。