好几天没有做每日一题了，因为周五有场比赛，然后周末出去浪了。
其实是因为这题卡住了。T-T

题意：
给一颗有n个点的树，每个点上有一个权值，记录1为根节点。现在有q次询问，每次询问（u,v,c）表示从u走到v，一路上遇到的点权如果比c大就选择购入珠宝，然后更新这个c，换句话说就是购入的时候的点权只能递增，问一共可以购入多少次。

思路：
参考了题解。
方法是树上倍增。（以前不怎么做这一类题目，因此研究了好久）
首先题目的意思要明确，题目保证从u走到v是往根节点走的，因此我们查找的时候方向是单向的。
那么我们需要知道的就是从u走到v能够购入多少个大小严格递增的珠宝。

我们利用倍增思想，构造一个f[i][j]表示从i出发，购入第2^j个珠宝的点是谁。
那么显然我们有f[i][j]=f[f[i][j-1]][j-1]，这是一个递推，如果我们知道f[i][0]，就可以推出剩下的了。

接下来考虑计算f[i][0]，显然根据定义我们可以知道f[i][0]表示从i出发购入的第一个珠宝的点的位置。
这里我们可以首先判断a[i]与a[fa[i]]的关系，如果有a[fa[i]]>a[i]，显然f[i][0]=fa[i]。fa[i]表示i的父亲节点。
否则我们需要往上查找，这里显然可以用倍增去找,由于fa[i]的情况已经算出来了，所以我们可以从fa[i]倍增查找，将k从大到小进行枚举，每次跳2^k判断a[f[fa][k]]与a[i]的大小，如果大于说明跳多了，那么减少k再跳，否则说明跳少了，可以先跳到f[fa][k]，然后继续跳。
这样子一遍dfs就可以预处理出f数组来。
最后考虑询问，对于每次询问手上的珠宝c，我们可以在dfs之前先把这个珠宝c作为一个点加入树中。
那么查询的时候，我们倍增地去跳就好了。注意这里要利用深度判断，因为仅通过f数组无法判断终点是否被跳过或者没有。

由于第一次写，所以很多细节其实都是参考别人代码的，下面会做注释。

类型：
树上倍增

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=100050;
int f[2*maxn][22],a[2*maxn];
int n,q,head[2*maxn],tot,dep[2*maxn];
struct node{
    int u,v,to,next;
}p[maxn*4];
struct Node{
    int u,v,c;
}p1[maxn];
void init(){
    memset(head,-1,sizeof(head));
    tot=0;
}
void add(int x,int y){
    tot++;
    p[tot].to=y;
    p[tot].next=head[x];
    head[x]=tot;
}
void dfs(int x,int fa,int d){
    int tmp=fa;
    for(int k=19;k>=0;k--){    //从大到小枚举跳的长度k
        if(f[tmp][k]&&a[f[tmp][k]]<=a[x])tmp=f[tmp][k];  
     //f[tmp][k]=0的话，说明已经跳出树的范围了。如果在范围内，判断跳到的点与x的大小
    }
    if(a[fa]>a[x])f[x][0]=fa;   //如果父亲节点比自己大，就设置成父亲节点
    else f[x][0]=f[tmp][0];    //如果父亲节点比自己小，就设置成查找出来的那个点

    for(int i=1;i<20;i++)f[x][i]=f[f[x][i-1]][i-1];   //递推处理所有长度的情况
    dep[x]=d;   //记录深度
    for(int i=head[x];~i;i=p[i].next){
        int y=p[i].to;
        if(y==fa)continue;
        dfs(y,x,d+1);
    }
}

int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    init();
    for(int i=1;i<=n-1;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    for(int i=1;i<=q;i++){
        cin>>p1[i].u>>p1[i].v>>p1[i].c;
        add(n+i,p1[i].u);
        add(p1[i].u,n+i);
        a[n+i]=p1[i].c;   //对于询问的点加入到树中
    }
    dfs(1,0,1);
    for(int i=1;i<=q;i++){
        int st,ed,ans=0;
        st=n+i;
        ed=p1[i].v;
        for(int k=19;k>=0;k--){
            if(dep[f[st][k]]>=dep[ed])st=f[st][k],ans+=(1<<k);   
           //如果当前跳完以后深度大于终点的深度，说明还得跳，并且把本次跳的结果加进来。
        }
        cout<<ans<<endl;
    }
    return 0;
}