城市网络
Problem:
有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。
你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。 在每次行程开始时，你手上有价值为 c 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 u 和 v ），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。
现在你想要对每一次行程，求出会进行多少次购买事件。
Input:
第一行，两个正整数 (n , q (2 ≤ n ≤ 10^5 , 1 ≤ q ≤ 10^5))。 第二行，n 个正整数 (a_i (1 ≤ a_i ≤ 10^5)) 描述每个城市售卖的珠宝的价值。 接下来 n-1 行，每行描述一条道路 (x , y (1 ≤ x,y ≤ n))，表示有一条连接 x 和 y 的道路。 接下来 q 行，每行描述一次行程 (u , v , c (1 ≤ u,v ≤ n , 1 ≤ c ≤ 10^5))。
Output:
对于每次行程输出一行，为所购买次数。
Example:
Input
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
Output
2
1
1
0
题解：
树上倍增，ST表，由于每次经过一个城市我们都会选择是否购买珠宝，决策后手上的珠宝都是经过路径上价值最大的珠宝，所以我们需要知道在需要经过的路径上，珠宝价值不断递增的城市有多少，本题如果用暴力方法，最差情况下会是O(n*q)的时间复杂度，显然这是不行的。本体应该用st表去维护每个节点上需要经过几个不断递增的节点，st表的递推式：
(st[i][j])表示从i点开始能买(2^j)个珠宝的点是哪个，所以如果一直(st[i][0])的值，那么i往上买(2^j)个珠宝的点，可以由i往上买(2^j-1)个珠宝的点再买(2^{j-1})个珠宝的点，所以递推式如上。对于(st[i][0])我们也可以用倍增的方式求，但是我们用从大到小枚举j值，这样就可以找到最远的可以买到1个珠宝的位置（如果枚举到的位置比当前权值小则需要继续向上倍增（倍增长度减少一半，因为原长度倍增的话则相当于已经倍增过的长度））。
经过ST表处理后的树，对于每次查询我们只需要查询从u开始，且深度大于等于v的点数之和（映射到ST表中就是满足条件的倍增长度的总和）。
关于ST表：https://www.cnblogs.com/LeafLove/p/12345136.html
Code：
/**********************************************************
* @Author: Kirito
* @Date: 2020-07-27 08:15:25
* @Last Modified by: Kirito
* @Last Modified time: 2020-07-27 09:27:55
* @Remark:
**********************************************************/
#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define CSE(x,y) memset(x,y,sizeof(x))
#define INF 0x3f3f3f3f
#define Abs(x) (x>=0?x:(-x))
#define FAST ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll , ll> pll;
const int maxn=211111;
vector<int> v[maxn];
int a[maxn],f[maxn][20],dep[maxn],to[maxn];
void dfs(int p,int fa)
{
int x=fa;
for(int k=19;k>=0;k--){
if(f[x][k]&&a[f[x][k]]<=a[p]) x=f[x][k];
}
if(a[x]>a[p]) f[p][0]=x;
else f[p][0]=f[x][0];
for(int i=1;i<20;i++)
f[p][i]=f[f[p][i-1]][i-1];
dep[p]=dep[fa]+1;
for(auto t:v[p]){
if(t==fa) continue;
dfs(t,p);
}
return;
}
int n,q;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.in","r",stdin);
#endif
FAST;
cin>>n>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=0;i<n-1;i++){
int x,y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=n+1;i<=n+q;i++){
int x,y,c;
cin>>x>>y>>c;
v[i].push_back(x);
v[x].push_back(i);
a[i]=c;
to[i-n]=y;
}
dfs(1,0);
for(int i=1;i<=q;i++){
int ans=0;
int x=i+n;
for(int k=19;k>=0;k--){
if(dep[f[x][k]]>=dep[to[i]]){
ans+=(1<<k);
x=f[x][k];
}
}
cout<<ans<<endl;
}
return 0;
}