简要题解：
1、
算法1：
首先考虑序列上的做法，我们可以把所有操作按左端点排序。然后从左到右扫描，并维护一个堆，遇到左端点，则将此操作的z的值的次数+1扔进堆里，遇到右端点，则将此操作的z值的次数-1扔进堆里。遇到点直接输出堆顶元素就行了。
再考虑树上的做法，如果我们把树划分成一些链的**，则所有的操作对于每条链是独立的，于是可以分别操作。而划分的链的方式如下：对于每个节点u，选取它的儿子里子树最大的那个。这样可以证明每个操作最多可以被分解到lgn条链上，再加上对于每条链的nlgn的操作，总时间复杂度是nlg^2n的。实现详见标程，证明详见漆子超2009年论文。
算法2（感谢@sillycross 告诉我这个做法）：
考虑将每个询问转化为从根到i的一个询问。然后对于每个节点维护一个数据结构，启发式合并即可。
2、
首先可以观察出两个结论：
1.最优**里每个数最多只有两个不同的质因子
2.这两个质因子一定一个<sqrt(n)，一个>sqrt(n)
然后对于所有素数建一个二分图，跑出来最大费用流即可。注意不要忘记考虑单个素数的情况。
但是此时n比较大，裸的费用流应该会超时。所以要提前排除掉一定在最优**中的数和一定不再最优**中的数。
对于第一类数，即为>n/2的素数，而且u为素数且u*i均一定不会写
对于第二类数，即为u = p1^a1 * p2^a2 *...*pk^ak，可以从把pi划分成子集，而且每个子集的最优结果之和大于u。这个计算方法就是对于每个数暴力dfs划分的子集，再加上hash就行了。
3、
题目的要求实际上就是对于每个i，a[i] >= a[j] （j >= i + 1）
然后考虑设计状态f[i][j]表示前i个数，最大不超过j的方案数
转移方程即为f[i][j] = f[i][j - 1] + f[i - 1][j - 1] + f[i - 2][1..j - 1]
意思就是没有大小为j的方案数 + j放在i的方案数 + j放在i - 1的方案数
利用前缀和即可优化为n^2
数据 + 标程：http:
//dl.
vmall.
com/
c0thafw6y3
1、
算法1：
首先考虑序列上的做法，我们可以把所有操作按左端点排序。然后从左到右扫描，并维护一个堆，遇到左端点，则将此操作的z的值的次数+1扔进堆里，遇到右端点，则将此操作的z值的次数-1扔进堆里。遇到点直接输出堆顶元素就行了。
再考虑树上的做法，如果我们把树划分成一些链的**，则所有的操作对于每条链是独立的，于是可以分别操作。而划分的链的方式如下：对于每个节点u，选取它的儿子里子树最大的那个。这样可以证明每个操作最多可以被分解到lgn条链上，再加上对于每条链的nlgn的操作，总时间复杂度是nlg^2n的。实现详见标程，证明详见漆子超2009年论文。
算法2（感谢@sillycross 告诉我这个做法）：
考虑将每个询问转化为从根到i的一个询问。然后对于每个节点维护一个数据结构，启发式合并即可。
2、
首先可以观察出两个结论：
1.最优**里每个数最多只有两个不同的质因子
2.这两个质因子一定一个<sqrt(n)，一个>sqrt(n)
然后对于所有素数建一个二分图，跑出来最大费用流即可。注意不要忘记考虑单个素数的情况。
但是此时n比较大，裸的费用流应该会超时。所以要提前排除掉一定在最优**中的数和一定不再最优**中的数。
对于第一类数，即为>n/2的素数，而且u为素数且u*i均一定不会写
对于第二类数，即为u = p1^a1 * p2^a2 *...*pk^ak，可以从把pi划分成子集，而且每个子集的最优结果之和大于u。这个计算方法就是对于每个数暴力dfs划分的子集，再加上hash就行了。
3、
题目的要求实际上就是对于每个i，a[i] >= a[j] （j >= i + 1）
然后考虑设计状态f[i][j]表示前i个数，最大不超过j的方案数
转移方程即为f[i][j] = f[i][j - 1] + f[i - 1][j - 1] + f[i - 2][1..j - 1]
意思就是没有大小为j的方案数 + j放在i的方案数 + j放在i - 1的方案数
利用前缀和即可优化为n^2
数据 + 标程：http:
//dl.
vmall.
com/
c0thafw6y3
被完虐
下次题解可以带个pascal么
