城市网络

感受
深深感觉到我很弱，树上倍增居然可以这样用！

如果想到倍增，应该就可以想到这个DP以及转移式。
但是存在一个问题：如何初始化dp[i][0]呢？

求解完DP后，如何求答案呢？
对于每一个询问q, u, v, c;
我们可以再u的后面加一个点r，然后从r开始往上跳

 #include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
struct edge{
    int v, nex;
}e[maxn << 1];
struct node{
    int u, v;
}b[maxn];
int a[maxn];
int n, q, cnt;
int head[maxn], dep[maxn];
void add_edge(int u, int v){
    cnt++;
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt;
}
int dp[maxn][25];
void dfs(int u, int f, int d){
    dep[u] = d;
    /**
    求解dp[i][j] 从i这个位置再购买2^j的位置
    dp[i][0]
    **/
    if(a[u] < a[f]){
        dp[u][0] = f;
    }
    else{
        int x = f;
        for(int j = 19; j >= 0; j--){
            if(dp[x][j] && a[dp[x][j]] <= a[u]) x = dp[x][j];
        }
        dp[u][0] = dp[x][0];
    }
    for(int j = 1; j <= 19; j++){
        dp[u][j] = dp[dp[u][j - 1]][j - 1];
    }
    for(int i = head[u]; i > 0; i = e[i].nex){
        if(e[i].v == f) continue;
        dfs(e[i].v, u, d + 1);
    }
}
int main(){
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int u, v, c;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }
    for(int i = 1; i <= q; i++){
        scanf("%d%d%d", &u, &v, &c);
        a[n + i] = c;
        add_edge(u, n + i); add_edge(n + i, u);
        b[i] = (node){n + i, v};
    }
    dfs(1, 0, 1);
    int ans;
    for(int i = 1; i <= q; i++){
        u = b[i].u; v = b[i].v; ans = 0;
        for(int j = 19; j >= 0; j--){
            if(dep[dp[u][j]] >= dep[v]){
                u = dp[u][j]; ans += (1 << j);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}