【每日一题】城市网络 （倍增）

题意：给你以1为根的树，问u到v有多少个节点，权值严格大于路径上所有节点的权值和w。保证v在u到根节点的路径上。
首先我们考虑普通的解法，对于每一次询问，dfs从u节点到v节点，保存前缀最大值，那么当搜到的这个节点的权值大于前缀最大值时，答案加一，这样做的时间复杂度是o(nq)
code:

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e5+100;
vector<int>G[maxn];
int f[maxn],a[maxn];
void dfs(int u,int fa)
{
    f[u] = fa;
    for(int i=0;i<G[u].size();i++)
    {
        int v = G[u][i];
        if(v == fa)continue;
        dfs(v,u);
    }
}
void qu(int u,int v,int w)
{
    int mx = w;
    int ans = 0;
    while(u != f[v])
    {
        if(a[u] > mx)++ans;
        mx = max(mx,a[u]);
        u = f[u];
    }
    printf("%d\n",ans);
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
    }
    dfs(1,0);
    while(q--)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        qu(u,v,w);
    }
}

如何优化？倍增。f[i][j]代表的是从i节点往上严格比她大的第2^j个元素的编号，那么f[u][i] = f[f[u][i-1]][i-1]。关键是如何求出f[u][0]?因为f[fa][0-logn]都先于u求出来了，那么如果a[fa] > a[u]的话,f[u][0] = fa;否则就以fa为起点倍增求出第一个大于a[u]的元素编号赋给f[u][0],这样的时间复杂度时o(qlogn)。
code:

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e5+100;
int a[maxn],d[maxn];
vector<int>G[maxn];

int f[maxn][20],dep[maxn];
void dfs(int u,int fa,int ds)
{
    dep[u] = ds;
    int tt = fa;
    if(a[fa] > a[u])
        f[u][0] = fa;
    else
    {
        for(int i=19;~i;i--)
            if(f[fa][i] && a[f[fa][i]] <= a[u])fa = f[fa][i];
        f[u][0] = f[fa][0];
    }
    for(int i=1;i<20;i++)f[u][i] = f[f[u][i-1]][i-1];
    for(int i=0;i<G[u].size();i++)
    {
        if(G[u][i] == tt)continue;
        dfs(G[u][i],u,ds+1);
    }
}
int main()
{
    int n,q;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",a+i);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].pb(v);
        G[v].pb(u);
    }
    for(int i=1;i<=q;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        G[i+n].pb(u);
        G[u].pb(i+n);
        d[i] = v,a[i+n] = w;
    }
    dfs(1,0,1);
    for(int i=1;i<=q;i++)
    {
        int u = n+i,v = d[i],ans=0;
        for(int i=19;~i;i--)
            if(dep[f[u][i]] >= dep[v])u = f[u][i],ans+=1<<i;
        printf("%d\n",ans);
    }
}