牛客每日一题3.31 城市网络树上倍增

城市网络

https://ac.nowcoder.com/acm/problem/13331

时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format:
%lld

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

输入描述:

第一行，两个正整数 n , q (2 ≤ n ≤ 10^5^ , 1 ≤ q ≤ 10^5^)。第二行，n 个正整数 a_i (1 ≤
a_i ≤ 10^5) 描述每个城市售卖的珠宝的价值。接下来 n-1 行，每行描述一条道路 x , y (1 ≤ x,y ≤
n)，表示有一条连接 x 和 y 的道路。接下来 q 行，每行描述一次行程 u , v , c (1 ≤ u,v ≤ n , 1 ≤ c
≤ 10^5^)。

输出描述:

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

示例1
输入

输出

题解:
毋庸置疑就是用倍增来做
那什么是倍增呢？
（先挖个坑，有空做个倍增的讲解）
递推式fa[i][j] = fa[fa[i][j-1]][j - 1],只要倍增得到fa[i][0]就行，因为有了这个后面都可以推出
fa[i][j] 代表i节点往上走2^j的距离，且比当前大的点
每次查询时，在所有需要问的点加一条新点，连在u的下方，新点的权值就是询问的初始权值，从这个新点往上倍增就可以了

#include<bits/stdc++.h>
#include<vector>
const int maxn=2e5+2;
using namespace std;
int a[maxn];
int dis[maxn];
int fa[maxn][23];
int n,q;
int to[maxn];
vector<int> W[2*maxn];
void dfs(int u,int f)
{
    int pos=f;

    for(int i=21;i>=0;i--)
    {
        if(fa[pos][i]&&a[fa[pos][i]]<=a[u])
        pos=fa[pos][i];
    }
    if(a[pos]>a[u])fa[u][0]=f;
    else fa[u][0]=fa[pos][0];
    for(int i=1;fa[fa[u][i-1]][i-1];i++)
    {
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
        dis[u]=dis[f]+1;
    for(int v=0;v<W[u].size();v++)

    {
        if(W[u][v]==f)continue;
        dfs(W[u][v],u);
    }
}
int main()
{

    cin>>n>>q;

    for(int i = 1; i <= n; ++i) 
    {
        scanf("%d",&a[i]);

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

    for(int i =1; i <= q ; ++i){//增加新点
        int aa,b,c;
        scanf("%d%d%d",&aa,&b,&c);
        W[n+i].push_back(aa);
        W[aa].push_back(i+n);
        a[n+i] = c;
        to[n+i] = b;
    }
    dfs(1,0);
   int sum = 0; 
   int pos;
    for(int i = n+1; i <= n+q; ++i){
       pos=i;
      sum=0;
        for(int j = 21; j >= 0; --j){
            if(dis[fa[pos][j]] >= dis[to[i]]) {
                sum += (1 << j);
                pos= fa[pos][j];
            }
        }
        printf("%d\n",sum);
    }
    return 0;

}