2022牛客寒假算法基础集训营2 G. 小沙的身法（LCA）

链接：https://ac.nowcoder.com/acm/contest/23477/G
来源：牛客网

题目描述

? 小沙发现他打球打不赢别人，打架也打不赢别人，所以他去了少林寺学习身法，以求打球的时候可以跑的更快，打架的时候也可以跑的更快（bushi）。

? 少林寺的方丈告诉小沙，他这种情况可以练习跳木桩，少林寺的一共有nn个木桩，为了锻炼打球时的步伐，方丈严格限制的小沙的可移动路线，他规定小沙一定要按照他制定的方案来训练，否则小沙就会被方丈制裁。

? 小沙发现 方丈制定的路线是一个以一个点扩散开的树形结构，而小沙就需要在这一个树形结构上跳来跳去。由于两个木桩之间的间隔特别特别远，所以每次跳跃都只能在相邻的木桩之间移动。

? 以地面高度为例，如果地面的高度都视为00（平地），木桩的高度不一,我们视每个木桩高度为aiai，小沙每次从低处跳向高处都会消耗两地高度之差的体力，但是从高的跳向低的则不消耗体力。

? 小沙练习了许久，终于熟能生巧了。

? 于是他叫来了师傅，想要给师傅秀一吧。

? 师傅便给了他mm个考验 每个考验师傅都要他从地面上跳上指定的uu节点，然后最快速的速度跳向vv节点，然后回到地面，小沙心中也没底所以想问你他至少需要多少体力才能把这个考验完成。

? 每个考验均相互独立，小沙的体力不会受到上一次考验的影响。

输入描述:

首先输入两个整数1≤n≤106，1≤m≤1051≤n≤106，1≤m≤105分别代表木桩个数以及师傅的考验个数
第二行输入n个数字 代表第i号木桩的高度是1≤ai≤1091≤ai≤109
随后n-1行 每行两个数字x，y 代表第x号木桩和第y号木桩中间有一条师傅允许经过的路径（双向的）
紧接着的 m行每行两个数字代表着 u节点前往v节点

输出描述:

对于每一个考验输出一行对应的答案
（每个考验均相互独立）

示例1

输入

复制

5 3
1 2 3 4 5
1 3
2 4
3 5
5 2
1 5
1 2
4 2

输出

复制

5
5
4

裸的LCA，可惜比赛的时候没看...

只需要建立两个数组dist1和dist2，其中dist1存根到当前点的路径上每两个相邻节点的差的绝对值，dist2存根跳到当前点需要花费的体力值，这样从当前点到根的体力值也可以求出来了。这两个数组在LCA预处理DFS的时候就能顺便求出来。最后处理询问的时候\(a[x]+((dist1[x] - dist1[LCA]) - (dist2[x] - dist2[LCA])) + (dist2[y] - dist2[LCA])\)即为答案（即分成两段：x到LCA和LCA到y）。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 1000005
using namespace std;
int t, n, m, tot = 0, head[N], Next[N * 2], ver[N * 2], f[N][25], d[N];
long long dist1[N], dist2[N], a[N];
void add(int x,int y) {
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void dfs(int x,int pre, long long sum1, long long sum2) {//因为要记录时间戳，所以用dfs 
    dist1[x] = sum1, dist2[x] = sum2;
    for(int i = head[x]; i; i = Next[i])
    {
        int y = ver[i];
        if(y == pre) continue;
        d[y] = d[x] + 1;
        dist1[y] = dist1[x] + abs(a[y] - a[x]);
        dist2[y] = dist2[x] + (a[y] > a[x] ? a[y] - a[x] : 0);
        f[y][0]=x;
        for(int j = 1; j <= t; j++) f[y][j] = f[f[y][j - 1]][j - 1];
        dfs(y, x, dist1[y], dist2[y]);
    }
} 
int lca(int x, int y) {
    if(d[x] > d[y]) swap(x, y);
    for(int i = t; i >= 0; i--)
    {
        if(d[f[y][i]] >= d[x]) y = f[y][i];
    }
    if(x == y) return x;
    for(int i = t; i >= 0; i--)
        if(f[y][i] != f[x][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}
signed main() {
    int q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    d[1] = 1, dist1[1] = dist2[1] = 0;
    t=(int) (log(n) / log(2)) + 1;
    for(int i = 1; i <= n - 1; i++) {
        int x, y, z;
        scanf("%d%d", &x, &y);
        add(x, y);
        add(y, x);
    }
    dfs(1, 0, 0, 0);
    while(q--) {
        int x, y;
        cin >> x >> y;
        long long ans = 0;
        int LCA = lca(x, y);
        ans += a[x];
        ans += ((dist1[x] - dist1[LCA]) - (dist2[x] - dist2[LCA])) + dist2[y] - dist2[LCA];
        cout << ans << endl;
    }
    return 0;
}
图论—LCA题库—牛客

相关

标签