【每日一题】- 3.30

看到大家都有牛币，我也想来骗点

我的解法：

题目给的是一颗有根树，每次查询的 u,v 又在一条从根出发的链上, 那就可以通过 dfs 把链剖成一个序列，这个序列是动态的，达到一个点 x：b[++tot] = a[x]，这个点的子树走完了：tot--; 设 dp[x] 为 b[1....x] 中从 x 一直向前走需要买的次数，转移: dp[x] = dp[y] + 1 且 b[y] 是第一个大于 b[x] 的, 对于查询 u, v 的操作，只需要知道从 u 出发走到的终点 e 即可，答案就为: dp[pos[u]] - dp[pos[e]] + 1 , pos[x]表示 x 在b[]中的下标，容易发现：终点一定是 pos[v] - pos[u] 中的最大值，如果还能买只可能在 v 的祖先上了, 我们要做三种操作：动态维护序列，查询比一个值大且离它最近的位置，查询区间最大值的位置, 将查询离线线段树就好了

（1）如果强制在线，可以先处理出 dp 数组，树链剖分操作查询就好了
（2）如果 u，v 不在从根出发的一条链上，那就要先解决 原问题改为从 v 出发到 u 能买多少次：
按照上面的思路，我们得到了 b[] -> [v......x]，dfs 走到了点 u，变成了 [v......x u]，设 dp[x] 为 从 x 出发到 b[] 末尾需要买的次数，只需要考虑 u 对前面的那些位置的答案产生了影响，显然是从 u 向前走到第一个大于或等于 a[u] 的位置，对这个区间来说它是最大值，一定会走到它，和原题的推测一致，这相当于区间 +1；解决了这个，（2）问可以分解为 u 出发走到 lca(u,v)，又从 lca(u,v) 走到 v, 好像很完美

如果有人发现问题，欢迎指出

ps. 输出答案记得换行

代码：

#include <bits/stdc++.h>

#define x first
#define y second
#define pii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long LL;
const int maxn = 1e5+25;
int n,u,v,q,c,a[maxn],cnt,head[maxn];
struct edge{
    int to,nxt;
}e[maxn<<1];
struct node{
    int v,c,id;
};
inline void add(int u,int v){
    e[++cnt] = (edge){v,head[u]};
    head[u] = cnt;
}
vector<node> ve[maxn];
int tr[maxn<<2],idx[maxn<<2],b[maxn];
void updata(int l,int r,int pos,int x,int val){
    if(l == r){
        tr[x] = val; idx[x] = r;
        return ;
    }
    int mid = (l+r) >> 1;
    if(pos > mid) updata(mid+1,r,pos,x<<1|1,val);
    else updata(l,mid,pos,x<<1,val);
    if(tr[x<<1] > tr[x<<1|1]){tr[x]=tr[x<<1];idx[x]=idx[x<<1];}
    else {tr[x]=tr[x<<1|1];idx[x]=idx[x<<1|1];}
}
void query(int l,int r,int L,int R,int x,int val,int &d){
    if(l == r){ d = r; return ;}
    int mid = (l+r) >> 1;
    if(mid+1<=R&&r>=L&&tr[x<<1|1]>val) query(mid+1,r,L,R,x<<1|1,val,d);
    if(l<=R&&mid>=L&&tr[x<<1]>val&&!d) query(l,mid,L,R,x<<1,val,d);
}
void querymax(int l,int r,int L,int R,int x,int &maxd){
    if(l > R || r < L) return;
    if(l >= L && r <= R){
        if(tr[x] > b[maxd]) maxd = idx[x];
        return ;
    }
    int mid = (l+r) >> 1;
    querymax(mid+1,r,L,R,x<<1|1,maxd);
    querymax(l,mid,L,R,x<<1,maxd);
}
int dp[maxn],tot,ans[maxn],pos[maxn];
void dfs(int x,int fa){
    b[++tot] = a[x]; pos[x] = tot;
    int d = 0; query(1,maxn-10,1,tot-1,1,a[x],d);
    dp[tot] = dp[d] + 1;
    updata(1,maxn-10,tot,1,a[x]);
    for(int i = 0;i < sz(ve[x]); ++i){
        d = 0; query(1,maxn-10,pos[ve[x][i].v],tot,1,ve[x][i].c,d);
        int maxd = 0; querymax(1,maxn-10,pos[ve[x][i].v],tot,1,maxd);
        if(d) ans[ve[x][i].id] = dp[d] - dp[maxd] + 1;
    }
    for(int i = head[x];i > 0;i=e[i].nxt){
        int v = e[i].to; if(v == fa) continue;
        dfs(v,x);
    }
    updata(1,maxn-10,tot,1,0);
    tot--;
}
int main(){
    scanf("%d %d",&n,&q);
    for(int i = 1;i <= n; ++i) scanf("%d",a+i);
    for(int i = 1;i < n; ++i){
        scanf("%d %d",&u,&v);
        add(u,v); add(v,u);
    }
    for(int i = 1;i <= q; ++i){
        scanf("%d %d %d",&u,&v,&c);
        ve[u].push_back((node){v,c,i});
    }
    dfs(1,0);
    for(int i = 1;i <= q; ++i) printf("%d\n",ans[i]);
    return 0;
}