【每日一题】3月31日题目精讲 树上倍增 ST表
题号 NC13331
名称 城市网络
首先给大家道个歉，最开始这题数据有点问题，把什么暴力都放过去了……现在数据锅已修，请之前使用暴力，最坏可能达到O(nq)的算法的同学去重测一下呀！真的十分抱歉！
我们来先说说大家都喜闻乐见的暴力，因为题目说保证 v 在 u 前往根的最短路径上，所以只要一遍dfs维护出每个点的父亲，然后每次顺着父亲一路走上去就可以了，这个的复杂度最坏情况是O(nq)的（退化成一条链的情况），是过不了的（出题人一般是不可能放这种复杂度过去的，但是赛场上如果你没有别的办法的时候其实试一下也未尝不可，毕竟没ac不亏，ac了血赚。）
-------------------------------------------以下是讲倍增的分割线--------------------------------
本题用到的方法是树上倍增，在分析本题解法之前我们先来讲讲倍增这个算法思想：
倍增和分治是对称的算法思想，分治的意思是“分而治之”，是将一个大问题分解成若干个小问题，然后解决了小问题再将小问题的解合并为大问题的解，而倍增直接从小问题出发，层层合并成大问题的解（个人看来，一定程度上，你也可以认为倍增是分治的合并过程）。
倍增的最基础应用应该是ST表，这里也顺便介绍给大家：
ST 表（Sparse Table）实际上是一种动态规划的方法，或者说简单一点，是用统计的思想来解决问题，它主要用于求解区间最大/最下值问题（也可也用来求和或者其他的东西）。以求区间最大值为例，它的基本思想是：用
维护从从i开始长度为
的区间的最大值，例如
表示的是以1开始长度为2的区间的最大值，
表达的是以1开始长度为4的区间的最大值。我们可以看到 
每增加1，区间的长度乘以二，于是两个相邻区间合并就可以得到当前这个长度的区间的最大值了，也就是说)
，这样%7D)
的时间复杂度我们就可以维护出f数组。
我们来先说说大家都喜闻乐见的暴力，因为题目说保证 v 在 u 前往根的最短路径上，所以只要一遍dfs维护出每个点的父亲，然后每次顺着父亲一路走上去就可以了，这个的复杂度最坏情况是O(nq)的（退化成一条链的情况），是过不了的（出题人一般是不可能放这种复杂度过去的，但是赛场上如果你没有别的办法的时候其实试一下也未尝不可，毕竟没ac不亏，ac了血赚。）
-------------------------------------------以下是讲倍增的分割线--------------------------------
本题用到的方法是树上倍增，在分析本题解法之前我们先来讲讲倍增这个算法思想：
倍增和分治是对称的算法思想，分治的意思是“分而治之”，是将一个大问题分解成若干个小问题，然后解决了小问题再将小问题的解合并为大问题的解，而倍增直接从小问题出发，层层合并成大问题的解（个人看来，一定程度上，你也可以认为倍增是分治的合并过程）。
倍增的最基础应用应该是ST表，这里也顺便介绍给大家：
ST 表（Sparse Table）实际上是一种动态规划的方法，或者说简单一点，是用统计的思想来解决问题，它主要用于求解区间最大/最下值问题（也可也用来求和或者其他的东西）。以求区间最大值为例，它的基本思想是：用
知道了f数组我们怎么来求任意区间[l,r]的最大值呢？也很简单，我们用两个长度刚好大于(r-l+1)/2的区间拼起来就好了（一个左边界是l，一个右边界是r）
参考代码
void rmp_st(int n) //预处理ST表,数组中有n个元素
{
for(int i = 1; i <= n; i++) f[i][0] = a[i];
int m = (int)(log((double)n) / log(2.0));
for(int j = 1; j <= m; j++)//先循环j再循环i，因为必须要把长度为1的区间都算出来了才能求长度为2的
for(int i = 1; i+(1<<j)-1 <= n; i++)
f[i][j] = min(f[i][j-1], f[i+(1<<(j-12))][j-1]);
}
int rmp_find(int l, int r) //求区间 l 到 r 之间的最值
{
int k = (int)(log(1.0 * (r-l+1)) / log(2.0));
return min(f[l][k], f[r-(1<<k)+1][k]);
} ------------------------------------------------以下是本题题解的分界线-------------------------------------------------
做题的第一步是好好读题，而在读题过程中你需要将题目的信息转化成对你解题有用的信息，比如所“假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。”这句话实际上是说明你买到的珠宝的价值是递增的，而且请注意，不是求最长上升子序列哪一种，而是只要递增了就要选，而这个递增呢就会告诉你，如果你在A城市买了珠宝，那么从A往上走下一次在哪里卖珠宝或者你从A往上走x个城市能买到几个珠宝和你是从哪里走到A的并没有关系，而当我们从A 往上走的时候，A上方比他小的点也是没有意义的。
考虑用表示从i往上走，能买珠宝的第
个点是哪个，显然，如果我们知道每个
的值， 那么
(
往上的第
个点再往上个点)。那么怎么求呢？肯定不能暴力，因为暴力最坏情况可能会让你每次都跑到根（构造一条链，从根到叶子价值递增）。这个其实也可也倍增着跳——如果 的父亲fa比 大那自不必说，当i的父亲fa比 小，那么我们可以看fa的父亲向上走
（k从大到小枚举）个能买进的点的权值（即
），如果这个点权限比 点权值小，说明还需要往上走，就跳到f[fa] [k]上并把跳跃的长度减少一半(如果还是刚刚的跳跃高度，从f[fa] [k]往上跳
长度，实际上就是从fa跳
，相当于就是跳到
了）；如果这个点的权值比 大，说明跳多了，就只是把跳跃长度减少一半再看。
注意我这里说的跳跃长度都是按照能买东西的点的个数计数，相当于我的f数组其实是对原树进行了重建，每个点往上走1步都的连向的它能到的第一个比他大的点（这样理解也许会容易很多——即我们对原树进行变形，每个点都连向它上方第一个能买东西的点，构成一个新的森林，于是问题就变成了，从u走到自己上方深度不小于dep[v]的点需要经过多少个点）。
有了这个值之后我们要求从 u 往上走到 v 经过了多少点，也可也倍增去求了——即从 u 出发尝试往上跳 高度，如果已经跳过 v 了，就减小 k，如果没有跳到 v 的上方，就先跳上去再减小 k。 注意，因为f数组存的能买东西的点，很有可能v根本不在这里面，所有跳的时候是通过判断深度来判断是否结束的。
我手算了一组样例帮助大家理解，我记得是lrj的紫书里面说过，学习数据结构最好的办法就手画，希望大家能动起手来，多写写多画画。
做题的第一步是好好读题，而在读题过程中你需要将题目的信息转化成对你解题有用的信息，比如所“假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。”这句话实际上是说明你买到的珠宝的价值是递增的，而且请注意，不是求最长上升子序列哪一种，而是只要递增了就要选，而这个递增呢就会告诉你，如果你在A城市买了珠宝，那么从A往上走下一次在哪里卖珠宝或者你从A往上走x个城市能买到几个珠宝和你是从哪里走到A的并没有关系，而当我们从A 往上走的时候，A上方比他小的点也是没有意义的。
考虑用
注意我这里说的跳跃长度都是按照能买东西的点的个数计数，相当于我的f数组其实是对原树进行了重建，每个点往上走1步都的连向的它能到的第一个比他大的点（这样理解也许会容易很多——即我们对原树进行变形，每个点都连向它上方第一个能买东西的点，构成一个新的森林，于是问题就变成了，从u走到自己上方深度不小于dep[v]的点需要经过多少个点）。
有了这个值之后我们要求从 u 往上走到 v 经过了多少点，也可也倍增去求了——即从 u 出发尝试往上跳
我手算了一组样例帮助大家理解，我记得是lrj的紫书里面说过，学习数据结构最好的办法就手画，希望大家能动起手来，多写写多画画。
还要最后一个问题，题目说“每次行程开始时，你手上有价值为 c 的珠宝”这个限制怎么办？很简单，在 u 点的下方接一个权值为 c 的点，然后从这个点开始往上走就可以了！
------------------------------------------------看过大家题解之后的补充-------------------------------------------------
9楼的@AROY 同学在题解里贴了一道题目，推荐大家去做一下~
【再贴一道ST表，理解倍增思想】
给你一个长为 n 的序列 a 和一个常数k
有 m 次询问，每次查询一个区间 [l,r] 内所有数最少分成多少个连续段，使得每段的和都 <= k
如果这一次查询无解，输出"Chtholly"
看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在本讨论贴中提问！
活动奖励：
在牛客博客中写出题解，并回复地址审核通过可获得10-50牛币（依据题目难度和题解的内容而定）
本道题目4月7日中午12：00之前写的题解有获得牛币资格~
牛客博客开通方式
- 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
- 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
- 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴
https://blog.nowcoder.net/n/8528cf017ee148a1b98e994cd110335a
