牛客寒训营2 G(复习LCA了)

题目 题意: 给定n个点，每个点高度为ai。用n-1条边连接这n个点构成一棵树，规定如果从高度高的点跳向高度低的点，花费为0；从高度低的点跳向高度高的点，花费为高度的差值。现在有m次询问，从地面(地面高度为0)跳向点u，再从u跳向点v，求最小花费。 思路: 求LCA，发现光求个dist不够用，因为从下往上跳和从上往下跳不一样。分别预处理从两个方向跳到根的距离。 这样，我们就可以先让u向上跳到LCA处，之后再从LCA跳到v，距离用dist[] - dist[LCA]得到. 时间复杂度: O((n+m)logn) 代码:

// Problem: 小沙的身法
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23477/G
// Memory Limit: 524288 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i