城市网络

Problem:

有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。
你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。
在每次行程开始时，你手上有价值为 c 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 u 和 v ），
假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。
现在你想要对每一次行程，求出会进行多少次购买事件。

Solution:

题中给出了v是u的祖先节点,而我们要求的是从u到v节点中遇到比当前所有拥有的价值都大的珠宝就需要买入,所以暴力的方法就是
从u沿着父节点一直爬到v,遇到价值大于当前拥有的最大价值就购买,并将购买的变为最大的价值。最终统计买了多少次就是答案，
而这样的作法的复杂度为O（nq），其实从题中给出n，q的大小我们容易联想到能不能先进性预处理，然后在查询的时候快速的得到答案。
由于 v是u的祖先节点 所以我们容易想到的是lca中的一个熟悉的操作，就是从v跳到u，而不是从v一步一步走到u，所以我们可以利用其中
的跳表实现（ST表）。
ST表的方程为f[i][j] = k,表示的是i节点向上跳2^j个节点后的节点是k，明显此处并不能直接用这个进行求解，所以我们需要对其进行变换。
首先我们知道题目中要求的是每当遇到比自己手中价值大的珠宝就进行购买，问可以购买多少珠宝，所以我们可以将方程变为当前节点i购买了
2^j个珠宝后的节点是k，那么我们只需要知道了f[i][0]的值是多少，剩下的就可以根据递推式f[i][j] = f[f[i][j - 1]][j - 1]求得。
递推式的理解为第i个节点购买2^j个珠宝后在的节点 = 第i个节点购买2^(j-1)个珠宝后的节点再购买2^(j-1)个珠宝的节点。

f[i][0]即从i节点只够买一个珠宝后的节点是哪个节点，而求解即为从i节点向上第一个大于i节点价值的节点是哪个节点，直接向上遍历一定是不行的，
所以我们需要用其它的方法求得，我们已经知道i的父节点到根节点的f数组的值，那么能否用它来求解呢？
如果i节点的父节点价值大于i节点，那么f[i][0] = i的父节点
否则，我们需要利用i的父节点找到一个价值大于i节点的价值的节点，而且必须时从i到根节点的第一个，所以我们需要让i的父节点用f表向上跳，
跳到一个点的价值是大于i节点的（i节点的价值大于i的父节点，而i父节点用f数组向上跳的时候价值一定是递增的）。在跳的时候f的第二维要从大到小，
这个学过倍增的应该能够理解。

tip：题中给了一个初始珠宝价值，所以我们每次查询的时候应该从初始珠宝价值的节点开始查询，因此我们需要在u节点连接一个价值为给出价值的儿子节点 。

// https://ac.nowcoder.com/acm/problem/13331
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Ri(x,y) scanf("%d%d",&x,&y)
#define Ri(x,y,z) scanf("%d%d",&x,&y,&z)
#define INF 0x3f3f3f3f
using namespace std;
template<class T>inline void read(T &res)
{
    char c;T flag=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef long long ll;
const int maxn = 1e5 + 10;
int a[maxn << 1];
vector<int> G[maxn << 1];
struct Query{
    int u,v,c;
    Query(){}
    Query(int _u,int _v,int _c):u(_u),v(_v),c(_c){}
}Q[maxn];
int f[maxn << 1][25],dep[maxn << 1],lg[maxn << 1];
void dfs(int nowp,int fa){
    dep[nowp] = dep[fa] + 1;
    if(a[nowp] < a[fa]){
        f[nowp][0] = fa;
    }else{
        int p = fa;
        per(i,lg[dep[nowp]],0){
            if(f[p][i] && a[nowp] >= a[f[p][i]]){// f[p][i]表示p点存在获得2^i个珠宝的那个点， a[nowp] >= a[f[p][i]]表示要是跳到之后价值还是比nowp小，那么需要接着跳 
                p = f[p][i];
            }
        }
        f[nowp][0] = f[p][0];// 上面最后一个if并未更新p，所以最终求得的点是p得到1个珠宝的那个点 
    }
    rep(i,1,lg[dep[nowp]]){
        f[nowp][i] = f[f[nowp][i - 1]][i - 1];
    }
    _for(i,0,G[nowp].size()){
        if(G[nowp][i] != fa){
            dfs(G[nowp][i],nowp);
        }
    }
}
int main(){
    IOS;
    lg[0] = -1;
    _for(i,1,maxn){
        lg[i] = lg[i >> 1] + 1;
    }
    int n,q;
    cin>>n>>q;
    rep(i,1,n){
        cin>>a[i];
    }
    int x,y;
    rep(i,2,n){
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int u,v,c;
    rep(i,1,q){
        cin>>u>>v>>c;
        G[n + i].push_back(u);
        G[u].push_back(n + i);
        a[n + i] = c;
        Q[i] = Query(n + i,v,c);
    }
    dfs(1,0);
    int ans;
    rep(i,1,q){
        ans = 0;
        u = Q[i].u;
        v = Q[i].v;
        per(j,lg[dep[u]],0){
            if(f[u][j] && dep[f[u][j]] >= dep[v]){
                ans += (1 << j);
                u = f[u][j];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}
/**
Problem:

有一个树状的城市网络（即 n 个城市由 n-1 条道路连接的连通图），首都为 1 号城市，每个城市售卖价值为 a_i 的珠宝。
你是一个珠宝商，现在安排有 q 次行程，每次行程为从 u 号城市前往 v 号城市（走最短路径），保证 v 在 u 前往首都的最短路径上。 
在每次行程开始时，你手上有价值为 c 的珠宝（每次行程可能不同），并且每经过一个城市时（包括 u 和 v ），
假如那个城市中售卖的珠宝比你现在手上的每一种珠宝都要优秀（价值更高，即严格大于），那么你就会选择购入。
现在你想要对每一次行程，求出会进行多少次购买事件。

Solution: 

题中给出了v是u的祖先节点,而我们要求的是从u到v节点中遇到比当前所有拥有的价值都大的珠宝就需要买入,所以暴力的方法就是
从u沿着父节点一直爬到v,遇到价值大于当前拥有的最大价值就购买,并将购买的变为最大的价值。最终统计买了多少次就是答案，
而这样的作法的复杂度为O（nq），其实从题中给出n，q的大小我们容易联想到能不能先进性预处理，然后在查询的时候快速的得到答案。
由于 v是u的祖先节点 所以我们容易想到的是lca中的一个熟悉的操作，就是从v跳到u，而不是从v一步一步走到u，所以我们可以利用其中
的跳表实现（ST表）。
ST表的方程为f[i][j] = k,表示的是i节点向上跳2^j个节点后的节点是k，明显此处并不能直接用这个进行求解，所以我们需要对其进行变换。
首先我们知道题目中要求的是每当遇到比自己手中价值大的珠宝就进行购买，问可以购买多少珠宝，所以我们可以将方程变为当前节点i购买了
2^j个珠宝后的节点是k，那么我们只需要知道了f[i][0]的值是多少，剩下的就可以根据递推式f[i][j] = f[f[i][j - 1]][j - 1]求得。
递推式的理解为第i个节点购买2^j个珠宝后在的节点 = 第i个节点购买2^(j-1)个珠宝后的节点再购买2^(j-1)个珠宝的节点。

f[i][0]即从i节点只够买一个珠宝后的节点是哪个节点，而求解即为从i节点向上第一个大于i节点价值的节点是哪个节点，直接向上遍历一定是不行的，
所以我们需要用其它的方法求得，我们已经知道i的父节点到根节点的f数组的值，那么能否用它来求解呢？
如果i节点的父节点价值大于i节点，那么f[i][0] = i的父节点
否则，我们需要利用i的父节点找到一个价值大于i节点的价值的节点，而且必须时从i到根节点的第一个，所以我们需要让i的父节点用f表向上跳，
跳到一个点的价值是大于i节点的（i节点的价值大于i的父节点，而i父节点用f数组向上跳的时候价值一定是递增的）。在跳的时候f的第二维要从大到小，
这个学过倍增的应该能够理解。 


tip：题中给了一个初始珠宝价值，所以我们每次查询的时候应该从初始珠宝价值的节点开始查询，因此我们需要在u节点连接一个价值为给出价值的儿子节点 。 


*/