题目：

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

做法：

下手慢了，数据更新了，暴力跑不动了。/(ㄒoㄒ)/~~

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
const int N = 2e5 + 7;
int n, q, val[N], mrk[N];
vector<int> g[N];
int fa[N][20], dep[N];
//fa[u][i]:保存u结点往根方向第2^i个val大于它的结点
void dfs(int u, int p){
    dep[u] = dep[p] + 1;//记录深度
    if (val[u] < val[p]){
        fa[u][0] = p;//若父节点p的val比u的val大，fa[u][0] = p
    }else{
        int x = p;
        for (int i = 19; i >= 0; --i){//x逼近第一个比val[u]大的结点下方的结点
            if (fa[x][i] && val[u] >= val[fa[x][i]]){
                x = fa[x][i];
            }
        }
        fa[u][0] = fa[x][0];//得到第一个比val[u]的的祖先结点
    }
    for (int i = 1; i <= 19; ++i){//倍增数组，递推
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (int i = 0; i < g[u].size(); ++i){
        int v = g[u][i];
        if (v == p) continue;
        dfs(v, u);
    }
}
int main(void){
    IOS;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> val[i];
    for (int i = 0; i < n-1; ++i){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= q; ++i){
        int u, v, c; cin >> u >> v >> c;
        g[n+i].push_back(u);//每个询问新加一个结点连在u下面
        g[u].push_back(n+i);
        val[n+i] = c, mrk[i] = v;//新结点val设为c，记录目标祖先v
    }
    dfs(1, 0);//dfs预处理倍增数组
    for (int i = 1; i <= q; ++i){
        int u = n+i, v = mrk[i], ans = 0;
        for (int i = 19; i >= 0; --i){
            if (dep[fa[u][i]] >= dep[v]){//用倍增数组，从u往v跳
                u = fa[u][i];
                ans += (1<<i);//记录跳了多少步
            }
        }
        cout << ans << endl;
    }
    return 0;
}