《【每日一题】3月31日 城市网络》 倍增法

题目相信大家都看的懂
思路：
我们从几个点入手，剖析出这题的解题思路。
首先这是个树状网络，那么我们肯定可以从树的思路入手。
然后很重要的一点，，保证 v 在 u 前往首都的最短路径上。
那么很明显，v就是在u和根节点的路径上的一点。
那么就可以归到求LCA的问题了。
普通的往上跑，那么这题的数据范围会超时，所以我们用倍增来跳。
如何倍增？这题的一个限制条件就是珠宝大时才能买，如果小就相当于不存在。
所以我们就只向上去连大的珠宝点。
所以我们设置dp[i][j]表示节点i,向上购买到2^j个珠宝点时的节点.
那么从这里我们可见，我们的倍增连接应该是通过节点的珠宝价值来连接，而不是单纯的连接深度。
那我们就可以知道dp[i][0]就是节点i向上购入1（即2^0)个节点时的位置。
dp[i][1]就是节点i向上购入2(即2^1)个节点时的位置。
dp[i][2]就是节点i向上购入4（即2^2)个节点时的位置。
....
然后关于查询的处理，我们将查询的那个点的珠宝价值变成一个新的点，连入出发点u。
那么我们就可以用每个连入的查询点来进行我们的查询操作了。

Code:
#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<math.h>
#include<stack>
#include<map>
#include<limits.h>
#include<vector>
#include<string.h>
#include<string>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N = 1e5+5;
const int M = 1e6+5;
#define pi acos(-1)
#define INF 1e8
#define INM INT_MIN
#define pb(a)  push_back(a)
#define mk(a,b) make_pair(a,b)
#define dbg(x) cout << "now this num is " << x << endl;
#define met0(axx) memset(axx,0,sizeof(axx));
#define metf(axx) memset(axx,-1,sizeof(axx));
#define sd(ax) scanf("%d",&ax)
#define sld(ax) scanf("%lld",&ax)
#define sldd(ax,bx) scanf("%lld %lld",&ax,&bx)
#define sdd(ax,bx) scanf("%d %d",&ax,&bx)
#define sddd(ax,bx,cx) scanf("%d %d %d",&ax,&bx,&cx)
#define sfd(ax) scanf("%lf",&ax)
#define sfdd(ax,bx) scanf("%lf %lf",&ax,&bx)
#define pr(a) printf("%d\n",a)
#define plr(a) printf("%lld\n",a)
int a[N],deep[N],fa[N];//deep记录节点深度.fa记录的是我们接入的查询节点，方便后面倍增
vector<int> G[N];
int dp[N][21];
/*
dp记录的是,向上走的购买位置.
就是说dp[i][0]是dp上面的第一个比他珠宝数大的点。然后dp[i][1]就是第二个.
dp[i][2]就是第四个..以此类推.
*/
void dfs(int u,int fa)
{
    deep[u] = deep[fa]+1;
    if(a[fa] > a[u]) dp[u][0] = fa;
    else
    {
        int x = fa;
        for(int i=20;i>=0;--i) if(a[dp[x][i]] <= a[u] && dp[x][i] != 0) x = dp[x][i];//通过父节点往上跳.倍增试探
        dp[u][0] = dp[x][0];//如果上面的所有点都是比u的值小，那么dp[u][0]就是根节点的祖先
    } 
    for(int i=1;i<=20;++i)//倍增递推,因为根节点已经处理好了,那么i就可以从1开始了
    {
        dp[u][i] = dp[dp[u][i-1]][i-1];
    }
    for(int i=0;i<G[u].size();++i)
    {
        int y = G[u][i];
        if(y == fa) continue;
        dfs(y,u);
    }
}
int main()
{
    int n,q;sdd(n,q);
    for(int i=1;i<=n;++i) sd(a[i]);
    for(int i=1;i<n;++i)
    {
        int x,y;sdd(x,y);
        G[x].pb(y),G[y].pb(x);
    }
    for(int i=1;i<=q;++i)
    {
        int x,y,z;sddd(x,y,z);
        G[x].pb(i+n);
        a[i+n] = z;
        fa[i+n] = y;
    }
    dfs(1,0);
    for(int i=1;i<=q;++i)
    {
        int u = i+n,v = fa[i+n],ans = 0;
        for(int j=20;j>=0;--j)
        {
            if(deep[dp[u][j]] >= deep[v])//当前要跳去的节点深度比我们终点大，那么就可以跳去，因为还在它下面 
            {
                ans += (1<<j);
                u = dp[u][j];
            }
        }
        pr(ans);
    }
    system("pause");
    return 0;
}