【每日一题】3月31日题目精讲 树上倍增 ST表 （待补）

题目描述

有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 的珠宝。
你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。 在每次行程开始时，你手上有价值为 c 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 u 和 v ），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。
现在你想要对每一次行程，求出会进行多少次购买事件。

输入描述:

第一行，两个正整数
第二行，n 个正整数 描述每个城市售卖的珠宝的价值。
接下来 n-1 行，每行描述一条道路 ，表示有一条连接 x 和 y 的道路。
接下来 q 行，每行描述一次行程

输出描述:

对于每次行程输出一行，为所购买次数。

示例1

5 4
3 5 1 2 4
1 2
1 3
2 4
3 5
4 2 1
4 2 2
4 2 3
5 1 5

输出

2
1
1
0

题解

做题的第一步是好好读题，而在读题过程中你需要将题目的信息转化成对你解题有用的信息，比如所“假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。”这句话实际上是说明你买到的珠宝的价值是递增的，而且请注意，不是求最长上升子序列哪一种，而是只要递增了就要选，而这个递增呢就会告诉你，如果你在A城市买了珠宝，那么从A往上走下一次在哪里卖珠宝或者你从A往上走x个城市能买到几个珠宝和你是从哪里走到A的并没有关系，而当我们从A 往上走的时候，A上方比他小的点也是没有意义的。

考虑用f[i][j]表示从i往上走，能买珠宝的第个点是哪个，显然，如果我们知道每个f[i][0]的值， 那么f[i][j]=f[f[i][j−1]][j−1] (i 往上的第个点再往上个点)。

那么f[i][0]怎么求呢？肯定不能暴力，因为暴力最坏情况可能会让你每次都跑到根（构造一条链，从根到叶子价值递增）。