城市网络

题意

在一颗树上面，求节点到节点的最大值的变化次数。

分析

先看一波题解

首先我们发现一定是节点的祖先，所以我们可以利用倍增的思想（类似于求），

首先我们先定义一个节点的父亲是在该路径上第一个大于当前节点的值的节点。

然后我们可以利用倍增的思想，求出第个购入节点。

然后就像求一样去往根节点跳就好了。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,q,t=17;

int a[maxn],b[maxn];

vector<int> v[maxn];

int d[maxn],fa[maxn][20];

void dfs(int u,int pre)
{
    d[u] = d[pre]+1;

    //先求出u的向上节点中，第一个值大于u的节点
    int x = pre;
    for(int i = t; i >= 0; i--)
    {
        if(fa[x][i] && a[fa[x][i]] <= a[u]) x = fa[x][i];
    }
    if(a[x] > a[u]) fa[u][0] = x;
    else fa[u][0] = fa[x][0];
    for(int i = 1;i <= t; i++)
    {
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }

    for(auto i : v[u])
    {
        if(i == pre) continue;
        dfs(i,u);
    }
}

signed main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i = 1; i <= n; i++) 
    {
        cin>>a[i];
    }
    for(int i = 1,x,y; i < n; i++) 
    {
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 1,x,y,z; i <= q; i++) 
    {
        cin>>x>>y>>z;
        //新建一个节点
        b[i] = y;
        v[x].push_back(i+n);
        v[i+n].push_back(x);
        a[i+n] = z;
    }
    dfs(1,0);
    for(int i = 1; i <= q; i++) 
    {
        //起点i+n，终点b[i]
        int u = i+n,to = b[i];
        int ans = 0;
        for(int i = t; i >= 0; i--)
        {
            if(d[fa[u][i]] >= d[to])
            {
                u = fa[u][i];
                ans += (1ll<<i);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}