周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。

大家纷纷觉得这个游戏非常符合同学们的特色，但只是扔硬币实在是太单调了。

同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币，其他同学记录下正反面情况。

用 表示正面朝上， 用 表示反面朝上，扔很多次硬币后，会得到一个硬币序列。比如 表示第一次正面朝上，后两次反面朝上。

但扔到什么时候停止呢？大家提议，选出 $n$ 个同学， 每个同学猜一个长度为 $m$ 的序列，当某一个同学猜的序列在硬币序列中出现时，就不再扔硬币了，并且这个同学胜利。为了保证只有一个同学胜利，同学们猜的 $n$ 个序列两两不同。

很快，$n$个同学猜好序列，然后进入了紧张而又刺激的扔硬币环节。你想知道，如果硬币正反面朝上的概率相同，每个同学胜利的概率是多少。

学校组织了一次新生舞会，Cathy 作为经验丰富的老学姐，负责为同学们安排舞伴。

有 $n$ 个男生和 $n$ 个女生参加舞会，一个男生和一个女生一起跳舞，互为舞伴。
Cathy 收集了这些同学之间的关系，比如两个人之前是否认识，计算得出 $a_{i, j}$，表示第 $i$ 个男生和第 $j$ 个女生一起跳舞时他们喜悦程度。
Cathy 还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 $b_{i, j}$ 表示第 $i$ 个男生和第 $j$ 个女生一起跳舞时的不协调裎度。

当然，还需要考虑很多其他间题。

Cathy 想先用一个程序通过 $a_{i, j}$ 和 $b_{i, j}$ 求出一种方案，再手动对方案进行微调。
Cathy 找到你，希望你帮她写那个程序。

一个方案中有 $n$ 对舞伴，假设每对舞伴的喜悦程度分别是 $a'_1, a'_2, \ldots, a'_n$，假设每对舞伴不协调程度分别是 $b'_1, b'_2, \ldots, b'_n$。令

$C = \frac{a'_1 + a'_2 + \cdots + a'_n}{b'_1 + b'_2 + \cdots + b'_n}$

Cathy 希望 C 值最大。

Alice 想要得到一个长度为 $n$ 的序列，序列中的数都是不超过 $m$ 的正整数，而且这 $n$ 个数的和是 $p$ 的倍数。

Alice 还希望，这 $n$ 个数中，至少有一个数是质数。

Alice 想知道，有多少个序列满足她的要求。

Bob 有一棵 $n$ 个点的有根树，其中 $1$ 号点是根节点。Bob 在每个节点上涂了颜色，并且每个点上的颜色不同。

定义一条路径的权值是，这条路径上的点（包括起点和终点）共有多少种不同的颜色。

Bob 可能会进行这几种操作：

• $1 \ x$，把点 $x$ 到根节点的路径上的所有的点染上一种没有用过的新颜色；
• $2 \ x \ y$，求 $x$ 到 $y$ 的路径的权值；
• $3 \ x$，在以 $x$ 为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob 一共会进行 $m$ 次操作。

Doris 刚刚学习了 fibnacci 数列，用 $f[i]$ 表示数列的第 $i$ 项，那么：

$\begin{aligned} f[0] &= 0 \\\\ f[1] &= 1 \\\\ f[n] &= f[n - 1] + f[n - 2], n \geq 2 \end{aligned}$

Doris 用老师的超级计算机生成了一个 $n \times m$ 的表格，第 $i$ 行第 $j$ 列的格子中的数是 $f[\gcd(i, j)]$，其中 $\gcd(i, j)$ 表示 $i$ 与 $j$ 的最大公约数。

Doris 的表格中共有 $n \times m$ 个数，她想知道这些数的乘积是多少。

这些数的乘积实在是太大了，所以 Doris 只想知道乘积对 $1000000007$ 取模后的结果。

给定一棵 $n$ 个节点的树，每个节点上有颜色，要求支持两种操作：

1. 询问两点 $(u, v)$ 之间有多少段颜色
2. 将两点 $(u, v)$ 之间所有的节点的颜色染成 $c$

小 C 同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》是一个养成类游戏，需要玩家每天按时上线，完成打卡任务。

这个游戏的地图可以看作一棵包含 $n$ 个结点和 $n - 1$ 条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相可达。树上结点编号为从 $1$ 到 $n$ 的连续正整数。

现在有 $m$ 个玩家，第 $i$ 个玩家的起点为 $S_i$，终点为 $T_i$。每天打卡任务开始时，所有玩家在第 $0$ 秒同时从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。（由于地图是一棵树，所以每个人的路径是唯一的）

小 C 想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点 $j$ 的观察员会选择在第 $W_j$ 秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 $W_j$ 秒也理到达了结点 $j$。小 C 想知道每个观察员会观察到多少人？

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点 $j$ 作为终点的玩家：若他在第 $W_j$ 秒前到达终点，则在结点 $j$ 的观察员不能观察到该玩家；若他正好在第 $W_j$ 秒到达终点，则在结点 $j$ 的观察员可以观察到这个玩家。

LCT 学习笔记，防忘

S国有 $N$ 个城市，编号从$1$到$N$。城市间用$N - 1$条双向道路连接，满足从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教，S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。

给定一个序列，需要支持两种操作：

1. 询问给定区间 $[l, r]$ 中的最大子段和
2. 修改序列中某个元素的值