内存限制：64 MiB   时间限制：500 ms标准输入输出

题目描述

有一个树状的城市网络（即 nnn 个城市由 n−1n-1n−1 条道路连接的连通图），首都为 111 号城市，每个城市售卖价值为 aia_ia​i​​ 的珠宝。

你是一个珠宝商，现在安排有 qqq 次行程，每次行程为从 uuu 号城市前往 vvv 号城市（走最短路径），保证 vvv 在 uuu 前往首都的最短路径上。

在每次行程开始时，你手上有价值为 ccc 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 uuu 和 vvv），假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。

现在你想要对每一次行程，求出会进行多少次购买事件。

输入格式

第一行，两个正整数 n,qn , qn,q。

第二行，nnn 个正整数 aia_ia​i​​ 描述每个城市售卖的珠宝的价值。

接下来 n−1n-1n−1 行，每行描述一条道路 x,yx , yx,y (1≤x,y≤n1 \leq x , y \leq n1≤x,y≤n)，表示有一条连接 xxx 和 yyy 的道路。

接下来 qqq 行，每行描述一次行程 u,v,cu , v , cu,v,c (1≤u,v≤n1 \leq u , v \leq n1≤u,v≤n)。

输出格式

对于每次行程输出一行，为所购买次数。

样例

样例输入

5 43 5 1 2 41 21 32 43 54 2 14 2 24 2 35 1 5

样例输出

2110

数据范围与提示

对于 100%100 \%100% 的数据，保证 2≤n≤105,1≤q≤1052 \leq n \leq 10^5 , 1 \leq q \leq 10^52≤n≤10​5​​,1≤q≤10​5​​ , 1≤ai≤1051 \leq a_i \leq 10^51≤a​i​​≤10​5​​ , 1≤c≤1051 \leq c \leq 10^51≤c≤10​5​​。

 

将询问看作节点，c为点权，作为起点的孩子

倍增，找到第一个大于询问的点，以这个点为基础继续倍增

#include
          
           #include
           
            #define N 200001using namespace std;int p,fa[N<<1][20];int front[N<<1],nxt[N<<1],to[N<<1],tot,val[N<<1];int dia[N<<1],dep[N<<1],decc[N];void add(int u,int v){        to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;         to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;}void dfs(int x,int y){
         int pos=y;        for(int i=p;i>=0;i--)                 if(fa[pos][i] && dia[fa[pos][i]]<=dia[x]) pos=fa[pos][i];         if(dia[pos]>dia[x]) fa[x][0]=pos;        else fa[x][0]=fa[pos][0];        for(int i=1;fa[fa[x][i-1]][i-1];i++) fa[x][i]=fa[fa[x][i-1]][i-1];        dep[x]=dep[y]+1;        for(int i=front[x];i;i=nxt[i])                if(to[i]!=y) dfs(to[i],x);}                int main(){        int n,q;        scanf("%d%d",&n,&q);        for(int i=1;i<=n;i++) scanf("%d",&dia[i]);        int u,v;        for(int i=1;i
            
             =0;j--)                        if(dep[fa[pos][j]]>=dep[t])                                ans+=1<