2022牛客寒假算法基础集训营2 G.小沙的身法 LCA 树上前缀和

思路

注意模拟样例的时候不要把询问读成连边。。。

LCA板题，维护树上前缀和，按照题目要求先跳到 u u u再跳到 v v v，再调到地上。向高处跳需要消耗高度差的体力，向低处跳不消耗体力。

那么需要分三段进行计算：

• 地 → a \rightarrow a →a：需要消耗高度 a a a的体力。
• a → b a \rightarrow b a→b：求树上路径，首先从 a a a点跳到 L C A ( a , b ) LCA(a, b) LCA(a,b)，需要消耗 s u m [ a ] − s u m [ l c a ] sum[a] - sum[lca] sum[a]−sum[lca]，然后从 L C A ( a , b ) LCA(a,b) LCA(a,b)跳到 b b b，这里不能单纯的用 s u m [ b ] − s u m [ l c a ] sum[b] - sum[lca] sum[b]−sum[lca]，而是需要重新维护一个后缀和(子节点高度-父节点高度)，否则此时向低处跳也会被记录体力。
• b → b \rightarrow b→ 地：由于所以节点高度 > 0 >0 >0，所以跳到地上肯定不消耗体力。

Accepted Code

#include 
using namespace std;

const int N = 1e6 + 10;
int a[N], dep[N], acc[N][21];
long long sum[N][2];
int cnt = 20;

vector g[N];

inline int LCA(int u, int v){
    if(dep[u] = 0; i--){
        if(dep[acc[u][i]] >= dep[v]) u = acc[u][i];
    }
    if(u == v) return u;
    for(int i = cnt; i >= 0; i--){
        if(acc[u][i] != acc[v][i]) u = acc[u][i], v = acc[v][i];
    }
    return acc[u][0];
}

void dfs(int now, int fa){
    acc[now][0] = fa, dep[now] = dep[fa] + 1;
    for(auto nxt : g[now]){
        if(nxt == fa) continue;
        sum[nxt][0] = sum[now][0] + max(0ll, 1ll * (a[now] - a[nxt]));
        sum[nxt][1] = sum[now][1] + max(0ll, 1ll * (a[nxt] - a[now]));
        dfs(nxt, now);
    }
}

inline void solve(){
    ios_base::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    for(int i = 1; i > a[i];
    for(int i = 1; i > u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(1, 1);
    for(int i = 1; i > v;
        int lca = LCA(u, v);
        long long ans = a[u] + sum[u][0] - sum[lca][0] + sum[v][1] - sum[lca][1];
        cout