给出一棵 n 个结点的树，每个结点有一个颜色c_i。 询问 q 次，每次询问以 v 结点为根的子树中，出现次数 ≥k 的颜色有多少种。树的根节点是1。

输入描述:

一行两个整数n和m。

第二行n个整数c_i，表示每个节点的颜色。

接下来n-1行，每行两个整数，表示一条边。

接下来m行，每行两个整数v和k，表示一个询问。

1<=n,m,ci<=10^5

输出描述:

对于每个询问，输出一个结果。

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成

一些操作：

I. CHANGE u t : 把结点u的权值改为t

II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值

III. QSUM u v: 询问从点u到点v的路径上的节点的权值和

注意：从点u到点v的路径上的节点包括u和v本身

输入描述:

输入的第一行为一个整数n，表示节点的个数。接下来n–1行，每行2个整数a和b，表示节点a和节点b之间有

一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作

的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。

对于100％的数据，保证 1<=n<=30000, 0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

输出描述:

对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

给定一棵含有n个节点的树，边长都为1.

有m个询问，每次询问，给定两个点A和B

询问有多少个点到A和B的距离相同。。

输入描述:

第一行一个整数n
接下来n-1，每行两个整数，表示树上的一条边。
接下来一个整数m，表示询问个数。
接下来m行，每行两个整数A和B，表示询问树上有多少个点到A和距离与到B的距离相同
n,m<=10^5

输出描述:

对于每个询问，输出一个整数

有n*m的格子，并且是个跳格子的地方。每个格子有一个颜色c。现在你要从网格的左上角调到右下角，并且遵守以下规则：
设当前格子为(x,y)。
1)对于每次跳到的格子(tx,ty), tx>x, ty>y
2)对于每次跳到的格子(tx,ty), c[(tx,ty)]≠c[(x,y)]
问有多少种跳法。

输入描述:

第一行三个整数n,m,k,表示行和列以及颜色的范围[1,k]。
接下来n行，每行m个整数表示当前格子颜色。
对于100%的数据，n,m<=750, k<=n*m。

输出描述:

一个正整数s表示跳法数量。答案对10^9+7取模。

长度为n的序列a，将其分成连续的k段，每段的价值为其中数字种类的个数，求最大价值总和。
1<=<=35000, 1<=k<=min(n, 50), 1<=ai<=n

输入描述:

第一行两个整数n和k。
第二行n个整数，表示一个序列。

输出描述:

输出结果。

长度为m的递增子序列（M length Increase Subsequence），称为MIS。
求长度为n的序列，有多少个MIS。
子序列不需要在原序列中不需要连续，但要保证相对位置。

输入描述:

第一行两个整数n和m。

第二行n个整数，表示一个序列。

输出描述:

输出MIS的个数，结果对20140921取余。

最近lxhgww又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。
通过一段时间的观察，lxhgww预测到了未来T天内某只股票的走势，第i天的股票买入价为每股AP_i，第i天的股票卖出价为每股BP_i（数据保证对于每个i，都有），但是每天不能无限制地交易，于是股票交易所规定第i天的一次买入至多只能购买AS_i股，一次卖出至多只能卖出BS_i股。
另外，股票交易所还制定了两个规定。为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔W天，也就是说如果在第i天发生了交易，那么从第i+1天到第i+W天，均不能发生交易。同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过MaxP。
在第1天之前，lxhgww手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，
当然，T天以后，lxhgww想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

输入描述:

输入数据第一行包括3个整数，分别是T，MaxP，W。
接下来T行，第i行代表第i-1天的股票走势，每行4个整数，分别表示AP_i,BP_i,AS_i,BS_i。0<=W<T<=2000, 1<=MaxP<=2000, 1<=BPi<=APi<=1000, 1<=ASi<=BSi<=MaxP

输出描述:

输出数据为一行，包括1个数字，表示lxhgww能赚到的最多的钱数。

有一个体积为V的背包，有m种物品，每种物品有体积和价值，且数量一定。求背包能装下的最大价值。

输入描述:

第一行两个整数V和m。
接下来m行，每行3个整数，表示第i种物品的数量、体积和价值。
V<=10000，m<=500,个数、体积、价值不超过1000。

输出描述:

输出一个整数，表示背包能装下的最大价值。

n个人来到医院排队就就医，现在排在医院外面。每个病人的看病时间是T[i]。假设队伍是随机的（可能是1~n的任意一个排列），求每个人需要在外面等待时间的期望值。

输入描述:

第一行一个整数n表示人数（n≤1000）。
第二行n个整数，表示每个人就医需要花的时间Ti。

输出描述:

输出n个实数，表示每个人需要排队时间的期望值。结果保留2位小数。

给定一个整数n，每次操作可以对当前数进行除以它的某个因子。除以哪个因子是随机的，求把n变成1的期望步数。

输入描述:

第一行一个整数T，表示测试数据组数。
接下来T行，每行一个整数，表示n。
T,n<=100000

输出描述:

对于每组测试数据，输出一行表示把n变成1的期望操作次数。保留4位小数。