【每日一题】城市网络

戳我传送
题意：
给你一颗树,然后n个点,n-1条边.然后给你q组查询,每组查询给你三个数分别是:u,v,c 题目保证1是首都,并且u->v->1这种类型的查询（此时v是u的父亲），问你从u->v的最长上升子序列长度。

思路：
倍增+dfs
题目表明v一定在u去网1的最短路径上，如果从u一直往上走到v，再去判断到达的每一个城市，需不需要购买。
这种算法的极端情况，形成了一条长为n的链，时间复杂度达到了O(nq)，后面数据加强就会超时了。
正确的做法是用倍增，f[i][k]表示i结点的第 个比i大的父亲的位置（是那个结点），这个理解清楚看代码得看半天。
不难得出状态转移方程f[i][k]=f[f[i][k-1]][k-1]，就是i往上第，然后再往上 ，相当于i往上走了2个，不就是i往上 了吗。
知道了状态和状态转移方程，接下来要求的就是初始状态f[i][0]了。
求f[i][0]：（以分解代码的方式）

void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
for(int i=2;i<=n;++i) {
        int x,y;
        read(x),read(y);
        add(x,y);
    }

add是链式向前星存图常用的函数，下面的循环则是将输入的边存入图中，因为是无向边，所以一般都是x-y、y-x都存，我看大佬的代码发现这一题输入的边是父结点（包括根结点1）在左边，子节点在右边，所以直接存x-y就可以了，我觉得出题人应该没有想让我们这样写。

for(int i=1;i<=q;++i) {
        int x,y,c;
        read(x),read(y),read(c);
        add(x,i+n);
        a[i+n]=c;
        go[i]=y;
    }

在 u 点的下方接一个权值为 c 的点（u和i+n连一条边，u为父亲），然后计算答案时从这个点开始往上走就可以了！ a[i+n]记录的是第i次查询商人手中珠宝的价值，go[i]记录的是第i次查询商人要去的地方。

dfs(1,0);
void dfs(int p,int fa) {
    int x=fa;
    for(int i=19;i>=0;--i) if(f[x][i]&&a[f[x][i]]<=a[p]) x=f[x][i];//f[x][i]表示第2^i个
    if(a[x]>a[p])    f[p][0]=x;                                    //比x大的祖先的位置
    else f[p][0]=f[x][0];
    dep[p]=dep[fa]+1;//记录深度
    for(int i=1;i<20;++i) f[p][i]=f[f[p][i-1]][i-1];
    for(int i=head[p];i;i=Next[i])
        dfs(to[i],p);//查询儿子
}

预处理f [ ][ ]数组，再细分一下分析

 int x=fa;
for(int i=19;i>=0;--i) if(f[x][i]&&a[f[x][i]]<=a[p]) 
    x=f[x][i];

如果第 个比 x 大的祖先都比p小（前提是要有这个祖先），那么x跳到这个祖先的位置减少跳跃的幅度继续这个步骤。这就是这个代码的意思，最后得到的 x 可能是第一个大于p的结点的儿子（也可能x最后是1，但是a[1] < a[p]，没有影响），也可能是p的父亲比p大，所以x还是p的父亲。
这个倍增的循环就和二进制表示十进制差不多，只是这里是用二进制数来找十进制数的位置，假如我那个位子离我们11，二进制就是1011，找到的第一个位置是1也就是十进制数的8，第二个位置如果是1也就是4，8+4大于11，所以这个位置是0，第三个位置是1也就是2，第四个位置是1也就是1，8+2+1=11。先从小的开始找呢，会出现前三个都是1，也就是1+2+4=7，之后的位置如果取1会超过11，不取又会小于11，所以不能倒着。

if(a[x]>a[p])    f[p][0]=x;
else f[p][0]=f[x][0];

根据上面的解释，很容易理解这段代码，如果a[x]大于a[p]，表示x就是比p大的父亲，否则x就是第一个大于p的结点的儿子，而f[p][0]是表示第一个比p大的父亲的位置（比p大，比的是珠宝的价值）。

dep[p]=dep[fa]+1;

这个就是简单的记录这个结点的深度，在求答案的时候用到，因为商人走的是最短路，所以深度可以判断商人往前跳跃一定距离到达的城市会不会超过目的地。

for(int i=1;i<20;++i) f[p][i]=f[f[p][i-1]][i-1];
for(int i=head[p];i;i=Next[i])
    dfs(to[i],p);

第一个循环就是状态转移了，第二个循环则是对儿子进行操作。

for(int i=1;i<=q;++i) {
    int ans=0;
    int x=i+n;//询问的起点
    for(int k=19;k>=0;--k) if(dep[f[x][k]]>=dep[go[i]]) {
        ans+=(1<<k);
        x=f[x][k];
    }
    printf("%d\n",ans);
}

从 u 出发尝试往上跳 高度，如果已经跳过 v 了，就减小 k，如果没有跳到 v 的上方，就先跳上去再减小 k，从大往小去遍历的原因和上面求f [p][0]是一样的。
Code：

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
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;
}
int head[maxn],Next[maxn],to[maxn],tot;
int a[maxn],dep[maxn],go[maxn],f[maxn][20];
void dfs(int p,int fa) {
    int x=fa;
    for(int i=19;i>=0;--i) if(f[x][i]&&a[f[x][i]]<=a[p]) x=f[x][i];
    if(a[x]>a[p])    f[p][0]=x;
    else f[p][0]=f[x][0];
    dep[p]=dep[fa]+1;
    for(int i=1;i<20;++i) f[p][i]=f[f[p][i-1]][i-1];
    for(int i=head[p];i;i=Next[i])
        dfs(to[i],p);
}
void add(int x,int y) {
    to[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
int n,q;
int main() {
    read(n),read(q);
    for(int i=1;i<=n;++i) read(a[i]);
    for(int i=2;i<=n;++i) {
        int x,y;
        read(x),read(y);
        add(x,y);
    }
    for(int i=1;i<=q;++i) {
        int x,y,c;
        read(x),read(y),read(c);
        add(x,i+n);
        a[i+n]=c;
        go[i]=y;
    }
    dfs(1,0);
    for(int i=1;i<=q;++i) {
        int ans=0;
        int x=i+n;//询问的起点
        for(int k=19;k>=0;--k) if(dep[f[x][k]]>=dep[go[i]]) {
            ans+=(1<<k);
            x=f[x][k];
        }
        printf("%d\n",ans);
    }
    return 0;
}