牛客每日一题3.31 城市网络 树上倍增

https://blog.csdn.net/qq_43804974/article/details/105196280

数据修复后，之前的就T掉了~还是树上倍增，dp[i][j]就是节点i开始拿了2^j个物品后所在的位置，递推就是dp[i][j] = dp[dp[i][j-1]][j - 1];然后只要倍增得到dp[i][0]就可以了。对每个询问新建立节点，这样找答案就很方便，而且也不会出现错误答案，因为新建立的节点必定是叶子节点，所以不会对其他答案造成影响。还有就是倍增的时候可以利用lg[深度]去稍稍优化一下，下面代码跑了181ms

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<time.h>
#include<string>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define ll long long
#define double long double
using namespace std;
#define PI  3.1415926535898
#define eqs 1e-17
const long long max_ = 1e6 + 7;
int mod = 2014;
const int inf = 1e9 + 7;
const long long INF = 1e18;
int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch<'0' || ch>'9') {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0'&&ch <= '9') {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * f;
}
inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
inline int min(int a, int b) {
    return a < b ? a : b;
}
inline int max(int a, int b) {
    return a > b ? a : b;
}
int n, m, s, head[max_], xiann = 1, cnt = 1, deepth[max_], lg[max_], father[max_][50];
int dp[max_][50],node[max_];
struct k {
    int next, to;
}xian[max_];
inline void add_(int a, int b) {
    xian[xiann].next = head[a];
    xian[xiann].to = b;
    head[a] = xiann;
    xiann++;
}

void dfs(int now, int fa) {
    if (now == 4 || now == 7) {
        int t = 1;
    }
    deepth[now] = deepth[fa] + 1;
    if (node[now] < node[fa]) {
        dp[now][0] = fa;
    }
    else {

        int x = fa;
        for (register int i = lg[deepth[fa]] + 1; i >= 0; i--) {
            if (dp[x][i] && node[dp[x][i]] <= node[now])x = dp[x][i];
        }
        dp[now][0] = dp[x][0];
    }
    for (register int i = 1; i <= lg[deepth[now]] + 1; i++) {
        dp[now][i] = dp[dp[now][i - 1]][i - 1];
    }
    for (int i = head[now]; i; i = xian[i].next) {
        int to = xian[i].to;
        if (to != fa) {
            dfs(to, now);
        }
    }
}
int aim[max_];
signed main() {
    lg[0] = -1;
    n = read(); m = read(); 
    //lg是向下取整的 
    for (register int i = 1; i <= n + m + 1; i++) {
        lg[i] = lg[i >> 1] + 1;
    }
    for (int i = 1; i <= n; i++)node[i] = read();
    for (register int i = 1; i <= n - 1; i++) {
        int a = read(), b = read();
        add_(a, b);
        add_(b, a);
    }
    for (int i = 1; i <= m; i++) {
        int now = read(), to = read(), v = read();
        node[n + i] = v;
        aim[i] = to;
        add_(n + i, now);
        add_(now, n + i);
    }
    dfs(1, 0);
    for (int j = 1; j <= m; j++) {
        int now = j + n, to = aim[j];
        int ans = 0;
        for (register int i = lg[deepth[now]] + 1; i >= 0; i--) {
            if (dp[now][i] && deepth[to] <= deepth[dp[now][i]]) {
                ans += (1 << i); now = dp[now][i];
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}