题目:给你一颗树,然后n个点,n-1条边.然后给你q组查询,每组查询给你三个数分别是:u,v,c 题目保证1是首都,并且u->v->1这种类型的查询.问你从u->v的最长上升子序列长度..
接下来我来解说下题解吧,hhh,因为我不会,tcl..给题解增添细节;
题解的思路是 类似rmq的东西+二进制查找(自命名hhh)
一段代码一段代码来...保证萌新都懂~
因为查询是固定顺序的..所以是个有向图..其他代码照搬题解代码解释一下,然后大家自己敲一次吧~

 scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
    }

这段代码是输入每个点自带的权值,然后联通x<-y的路线

for (int i = n + 1; i <= n + q; i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        v[x].push_back(i);
        a[i] = c;
        to[i - n] = y;   //记录对应的终点
    }

这段代码是把q组输入的值存起来..考虑前面的点都是在1~n的范围内,我们创建新点在(n+1,n+q)把我们要查询的点变成新的节点放到x节点上,然后新的节点也自带权值,刚好符合题目进行查询..这个假如不懂可以先看后面的,看了后面的应该就懂了.

dfs(1, 0);
void dfs(int p, int fa)
{
    int x = fa;
    for (int k = 19; k >= 0; k--)
    if (f[x][k] && a[f[x][k]] <= a[p] ) x = f[x][k];   //如果x往上跳2^k步这个点存在，且这个点的权值比a[p]要小，就跳到这个点再往上跳
    if (a[x] > a[p]) f[p][0] = x;  //判断比a[p]大的点到底是x还是x的上面那个点
    else f[p][0] = f[x][0];
    //向上倍增的找到第一个比p权值大的点
    for (int i = 1; i < 20; i++) f[p][i] = f[f[p][i - 1]][i - 1];  //倍增的求出每个点向上2^j步的点
    dep[p] = dep[fa] + 1;   //维护高度
    int num = v[p].size();
    for (int i = 0; i < num; i++)
    {
        int to = v[p][i];
        dfs(to, p);   //搜儿子
    }
}

首先解释下f数组的含义,f[i][j]表示的i后面2^j后递增数列的值是多少..比方说1 3 4 5 6 2 8假如我的i是1,f[1][0]就是比它大2^0的位子的值,也就是3,f[1][1]那就是比它大2^1的位子的值,也就是4..再解释下p,fa,p是我当前搜询的这个节点,fa是我搜寻的那个节点的上一个节点..搜寻是从根节点到子节点慢慢来的..dep是记录我在那一层.比如我的树是一条链1<-2<-3<-5那么dep[1]=1;dep[2]=2;dep[3]=3;dep[5]=4;数组变量解释完了,dfs这个不懂那先别做这题..
x是找到第一个大于fa的节点..也就是f[fa][0];
下面我来解释这段代码:

for (int k = 19; k >= 0; k--)
    if (f[x][k] && a[f[x][k]] <= a[p] ) x = f[x][k];

大家都知道二进制可以表示任何十进制的数,这个也是一样的,不过是用二进制表示十进制位子所处的位子,假如我那个位子离我们11,我们应该怎么找到它呢？我们把11二进制分解就是1011那么我先找到第一位的1也就是8,第二位的1不能取哦..取了就是12了嘛~然后3,4位也取1就好了..解释下为什么要倒着取..就是准确的确定一个数必定要倒着取,因为你正着取,比如还是11,正着取,第一次取1,第二次我又取1,第三次我还是取1,7了,而第四个我就不能取了..这段代码解释完了..

f (a[x] > a[p]) f[p][0] = x;  
    else f[p][0] = f[x][0];

这段代码就比较简单了,就是确定f[p][0]的位子,假如大于fa节点的值假如不存在/存在..那么我就是比较下a[fa]和a[p]的大小..假如大于fa节点的第一个值/a[fa]小于a[p],那么肯定那个值是f[x][0]..而且是递归来的,那么上个转态的f[x][0]是存在的..这段代码解释完了..

    for (int i = 1; i < 20; i++) f[p][i] = f[f[p][i - 1]][i - 1];

这段代码的总用就是通过前面的状态和f[p][0]更新这个状态的全部状态..好吧,这里也给萌新详细解释一下..先解释下状态方程f[p][i] = f[f[p][i - 1]][i - 1],现在我的状态是p,那么我现在要求p递增序列的第2^i个是不是等于我求p后面2^(i-1)个再求2^(i-1)个？我现在知道了f[p][0]和f[<p][<20]那么我是不是就可以把现在的状态全部转移完了呢?

dep[p] = dep[fa] + 1;

这句话是求深度..也就是位于树的第几层..

    int num = v[p].size();
    for (int i = 0; i < num; i++)
    {
        int to = v[p][i];
        dfs(to, p);   //搜儿子
    }

这句话的意思就是搜儿子,找下一个点..
dfs部分是为了打一张表..一张知道所有点->到2^i（i<=19）的表..
接下来这部分代码是查询记录答案..

for (int i = 1; i <= q; i++)
    {
        int ans = 0;
        int x = i + n;   //i+n是第i个询问的起点
        for (int k = 19; k >= 0; k--)   //k从大到小枚举
            if (dep[f[x][k]] >= dep[to[i]])   //如果跳完之后深度小于目标点深度就已经走过了，跳跃高度要减小
            {
                ans += (1 << k);           //点数加2^k
                x = f[x][k];               //向上跳2^k个点
            }
        printf("%d\n", ans);
    }

这里的原理楼上介绍过了..我就不详细再重复一次了..ans每次查询先赋值为0..然后跳深度每次跳到比它大的地方,也就是楼上介绍的二进制..然后每次跳的是2^k答案就+2^k..
ac代码:

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define inf 132913423039
typedef long long ll;
const ll mod=1e9+7;
const ll N=1e6+5;
const double eps=1e-7;
using namespace std;
const int manx=1e7+5;
ll gcd(ll a,ll b) {return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b) { return a*b/gcd(a,b);    }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a = (a*a)%p;b >>= 1;}return ans%p;}
ll Inv(ll x)          { return qp(x,mod-2,mod);}
ll C(ll n,ll m){if (m>n) return 0;ll ans = 1;for (int i = 1; i <= m; ++i) ans=ans*Inv(i)%mod*(n-i+1)%mod;return ans%mod;}
vector<int> v[N];
int a[N], f[N][20], dep[N], to[N];
void dfs(int p, int fa)
{
    int x = fa;
    for (int k = 19; k >= 0; k--)
    if (f[x][k] && a[f[x][k]] <= a[p] ) x = f[x][k];   //如果x往上跳2^k步这个点存在，且这个点的权值比a[p]要小，就跳到这个点再往上跳
    if (a[x] > a[p]) f[p][0] = x;  //判断比a[p]大的点到底是x还是x的上面那个点
    else f[p][0] = f[x][0];
    //向上倍增的找到第一个比p权值大的点

    for (int i = 1; i < 20; i++) f[p][i] = f[f[p][i - 1]][i - 1];  //倍增的求出每个点向上2^j步的点

    dep[p] = dep[fa] + 1;   //维护高度

    int num = v[p].size();
    for (int i = 0; i < num; i++)
    {
        int to = v[p][i];
        dfs(to, p);   //搜儿子
    }
}
int n, q;
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++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
    }
    for (int i = n + 1; i <= n + q; i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        v[x].push_back(i);
        a[i] = c;
        to[i - n] = y;   //记录对应的终点
    }
    dfs(1, 0);
    for (int i = 1; i <= q; i++)
    {
        int ans = 0;
        int x = i + n;   //i+n是第i个询问的起点
        for (int k = 19; k >= 0; k--)   //k从大到小枚举
            if (dep[f[x][k]] >= dep[to[i]])   //如果跳完之后深度小于目标点深度就已经走过了，跳跃高度要减小
            {
                ans += (1 << k);           //点数加2^k
                x = f[x][k];               //向上跳2^k个点
            }
        printf("%d\n", ans);
    }
    return 0;
}

完结撒花~