NC13331 城市网络

题意

给定一棵树，有 个点，根节点为 ，每个节点有一个值 。
有 个询问，每个询问包含 ，问当前值为 ，从 走到 ，每次遇到比当前值大的值，即将当前值替换为该值，最终总共要替换多少次。（ 在 到根节点的路径上）

分析

这题还是很有必要记录一下的！
首先我们每次可以在 后面接一个点 ， 点的值为 ，相当于每次从 走向 。
然后暴力是 ，显然不可取。
但是如果我们能快速知道每个值往上走第一个比它大的值，就可以倍增来解决了。
问题是，怎么获取每个值往上走的第一个比它大的值呢？
注意到，比 大的第一个值，一定是 或这比 大的第 个值（ 为正整数，这里假设 的值为无穷大）。
于是，我们可以用倍增来求比 大的第一个点。
就是每次从父节点往上跑，如果某一段都比 小，那么答案肯定不在这一段里，否则答案肯定在这一段里。
有点二分的感觉。
处理完 表，回答询问就很简单了。就是深度满足就往上爬。
总复杂度

代码如下

#include <bits/stdc++.h>
#define N 300005
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
LL z = 1;
struct node{
    int a, b, n;
}d[N * 2];
int h[N], fa[N], w[N], q[N][2], st[N][20], dep[N], cnt;
void cr(int a, int b){
    d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
void dfs(int a){
    int i, b, t;
    if(w[a] < w[fa[a]]) st[a][0] = fa[a];
    else{
        t = fa[a];
        for(i = 19; i >= 0; i--){
            if(st[t][i] && w[st[t][i]] <= w[a]) t = st[t][i];
        }
        st[a][0] = st[t][0];
    }
    for(i = 1; i <= 19; i++) st[a][i] = st[st[a][i - 1]][i - 1];
    for(i = h[a]; i; i = d[i].n){
        b = d[i].b;
        if(b == fa[a]) continue;
        fa[b] = a;
        dep[b] = dep[a] + 1;
        dfs(b);
    }
}
int main(){
    int i, j, n, m, a, b, ans = 0;
    n = read(); m = read();
    for(i = 1; i <= n; i++) w[i] = read();
    for(i = 1; i < n; i++){
        a = read(); b = read();
        cr(a, b);
        cr(b, a);
    }
    for(i = 1; i <= m; i++){
        q[i][0] = read(); q[i][1] = read(); w[i + n] = read();
        cr(i + n, q[i][0]);
        cr(q[i][0], i + n);
    }
    dep[1] = 1;
    dfs(1);
    for(i = 1; i <= m; i++){
        ans = 0;
        a = i + n, b = q[i][1];
        for(j = 19; j >= 0; j--){
            if(dep[st[a][j]] >= dep[b]){
                a = st[a][j];
                ans += (1 << j);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}