【每日一题】3月31日

我们考虑一个暴力的做法：每次从这个点找到它上面的第一个比他大的点 跳过去。
但是这样显然是过不了的。我们先丢掉询问给出的那个权 每次就拿这个点上的权来跳 答案如何快速处理。
我们可以倍增： 往上找了 个答案之后的点在哪里。问题转化为处理

这个也可以利用我们前面已经求出的f来计算：观察到 随着 的递增而递增。所以我们可以用类似询问倍增的方式来做：每次枚举 比较 和当前点的权 决定跳不跳。

对于询问 题解里有一个很巧妙的做法：将每个点接在起点的下面就可以了（也可以每一次都先倍增找到第一个比它大的）

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 5e5 + 5;

struct Edge{
    int to,nxt;
}e[MAXN<<1];
int head[MAXN],cnt;

inline void add(int u,int v){
    e[++cnt] = (Edge){v,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,head[v]};head[v] = cnt;
}

int n;
int a[MAXN];
int b[MAXN],dep[MAXN],f[MAXN][20];

inline void dfs(int v,int fa=0){
    int t = fa;
    ROF(i,19,0){
        if(f[t][i] && a[f[t][i]] <= a[v]) t = f[t][i];
    }
    if(a[t] > a[v]) f[v][0] = t;
    else f[v][0] = f[t][0];
    FOR(i,1,19) f[v][i] = f[f[v][i-1]][i-1];
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa) continue;
        dep[e[i].to] = dep[v] + 1;dfs(e[i].to,v);
    }
}

int main(){
    int q;scanf("%d%d",&n,&q);
    FOR(i,1,n) scanf("%d",a+i);
    FOR(i,2,n){
        int u,v;scanf("%d%d",&u,&v);add(u,v);
    }
    FOR(i,n+1,n+q){
        int u,v,w;scanf("%d%d%d",&u,&v,&w);
        add(i,u);
        a[i] = w;b[i-n] = v;
    }
    dep[1] = 1;dfs(1,0);
    FOR(i,1,q){
        int ans = 0,v = i+n;
        ROF(k,19,0){
            if(dep[f[v][k]] >= dep[b[i]]){
                ans |= (1<<k);
                v = f[v][k];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}